컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/17829 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 문제 해결 알고리즘 전형적인 분할 정복 문제이다. 소스 코드 #include using namespace std; int arr[1100][1100]; void div_n_cnqr(int N, int x, int y){ if(N == 2){ vector v; v.push_back(arr[x][y]); v.push_back(arr[x+1][y]); v.push_..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 해결 알고리즘 분할정복으로 풀 수 있는 문제 아래 문제에서 9등분을 한다는 부분 빼고는 같은 유형의 문제였다. https://kimmessi.tistory.com/110 소스 코드 #include #define MAX 2188 using namespace std; int N; int arr[MAX][MAX]; int result[3]; void div_n_coqr(int n, in..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해결 알고리즘 nXn 사분면에서 모든 숫자들이 같지 않으면 또 사분면으로 나누어서 분할 정복을 실행해준다. 만약 같다면 그 숫자를 출력해준다. 소스 코드 #include #define MAX 65 using namespace std; int N; int arr[MAX][MAX]; void div_n_coqr(int n, int x, int y){ bool flag = true; ..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해결 알고리즘 큰 정사각형부터 분할정복 해가면서 전부 다 비어있으면 잘라진 정사각형에, 다 채워져있으면 파란색 정사각형에 +1을 해주고 만약 둘 다 아닐 경우 4분할해서 또 거기서 분할정복을 해준다. 소스 코드 #include using namespace std; int cnt_1 = 0, cnt_0 = 0; int arr[129][129]; void div_con..

분할정복(Divide and Conquer) 알고리즘이란? 문제의 입력사례를 두 개 이상 작은 입력사례로 분할한다. 계속 분할 하다가 바로 답을 얻을 수 있으면 원래 문제의 답은 얻은 답들을 통합해 구하는 알고리즘 하향식(top - down) 문제풀이 방식이다. 상위 입력사례의 해답은 하위의 작은 입력사례들의 해답을 가지고 구한다. 재귀함수의 작동원리가 이런데, 문제 풀이 중심으로 재귀함수를 작성한다. 이분 탐색(binary search) 재귀함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같다. 1. [분할(divide)] 배열을 정 가운데 원소를 기준으로 반으로 분할한다(divide). $x$가 가운데 원소보다 작으면 왼쪽 배열을 선택, $x$가 가운데 원소보다 크면 오른쪽 배열을 선택한..