(백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄

아직 못 푼 그리디 문제가 몇 개 있지만 잠시 묻어두고 분할 정복을 시작하고자 한다!

 

↓ 자세한 설명은 아래 라이님 블로그를 참고! ↓

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220776241154&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

분할 정복(Divide and Conquer) (수정: 2016-12-25)

 

분할 정복의 대표적인 예시

1. 병합 정렬(Merge Sort)

2. 이분 탐색(Binary Search)

3. 거듭제곱 연산(a^b)

 

Master Theorem

$T(n) = aT(\frac{n}{b}) + O(n^d)$,  $(a > 0, b > 1, d \geq 1) $

$\Rightarrow T(n) = \left\{\begin{matrix} O(n^d) & d > \log_{b}{a} \\ O(n^d\log{n}) & d = \log_{b}{a} \\ O(n^{\log_{b}{a}}) & d < \log_{b}{a}\\ \end{matrix}\right.$ 

 

즉, 문제 크기가 n인 문제를 a개의 $\frac{n}{b}$ 크기의 문제로 계속 나누고, 이를 합치는데 $O(n^d)$ 만큼이 소요된다면 Master Theorem에 의해 시간 복잡도를 설명할 수 있다는 이론이다.

 

증명은... 이산 수학에서 배울 수 있는데 다 필요없다. 

대신 생각해보면 상당히 당연한게, 시간 복잡도는 문제를 분할할 때의 시간복잡도와 문제를 병합할 때의 시간복잡도에 의존한다.

분할할 때의 시간 복잡도가 크면 분할 시간 복잡도를, 병합할 때의 시간 복잡도가 크면 병합 시간 복잡도를 따르며 이 둘이 같다면 둘 다 고려해주면 된다.

 

 

병합 정렬의 경우

1. 나누어지는 문제의 갯수 :  a = 2

2. 분할 후 문제의 크기 : $\frac{N}{b}$, b = 2

3. 각 문제마다 병합 단계에서 걸리는 시간 : $O(N)$, d = 1

→ $d =\log_{b}{a}$  이므로 병합정렬의 시간 복잡도는 $O(Nlog{N})$

 

이분 탐색의 경우

1. 나누어지는 문제의 갯수 :  a = 1

2. 분할 후 문제의 크기 : $\frac{N}{b}$, b = 2

3. 각 문제마다 병합 단계에서 걸리는 시간 : N/A, d = 0

→  $d =\log_{b}{a}$ 이므로 병합정렬의 시간 복잡도는 $O(log{N})$

 

히스토그램 문제의 경우(라이님 블로그 참고)

1. 나누어지는 문제의 갯수 :  a = 2

2. 분할 후 문제의 크기 : $\frac{N}{b}$, b = 2

3. 각 문제마다 병합 단계에서 걸리는 시간 : N/A, d = $O(N)$, d = 1

→  $d =\log_{b}{a}$  이므로 병합정렬의 시간 복잡도는 $O(Nlog{N})$

 

우선 라이님의 히스토그램 문제 코드를 보면서 따라해야겠다고 생각한 점 

0. 꼭 미리 앞에서 정의해야하는 변수가 아니라면 즉석에서 정의함  → 코드의 가독성 ↑

1. 함수 앞에 함수의 기능을 설명하는 주석 설명

2. [분할정복] base case를 제시 →  이후 재귀함수를 이용 →  이외 경우 (이 문제에서는 양쪽 구간에 걸쳐 있는 답 찾기)

3. 변수명(s, e , l, r, w) & 범위 [s, e)

s- start / e-end  / mid = (s+e) /2

l - left / r - right

w = 1 (width를 1로 정의해줌으로써 1의 의미를 명확하게 만들어줌)

 

백준 1992번

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

정답률이 높기도 하고, 어릴 때의 내가 풀었길래 냉큼 도전했는데ㅋㅋㅋㅋ2시간 반 걸렸다.

디버깅하는데 거의 1시간은 쓴 듯..

 

틀린 곳이 input 부분이랑 for loop시작값이라서 너무 허무했따🥲 그래도 풀었으니 됐찌!!

 

⛔ (특히 디버깅 매우 오래 걸린 입력 부분 실수) ⛔

input을 Arr[64][64]에 직접 받으면 안된다.

input에 공백이 없기 때문에(아니 이거 너무해🥶) 11110000을 1 4개, 0 4개로 받는 대신 11,110,000으로 받기 때문에 이 부분을 잘 생각해서 input을 받아야 한다. 

 

(참고로 위에 라이님 코딩 배울 점에서 착안해서 코드를 작성했는데, 생각보다 금방 짤 수 있어서 놀랐따!! 디버깅이 오래 걸려서 그렇ㅈ..ㅣ...)  

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <utility>
#include <vector>

// QuadTree를 분할정복으로 만드는 함수
void QuadTree(int Arr[][64], int N, int x, int y) { // 배열과 배열의 크기
	if (N == 1) { printf("%d", Arr[x][y]); return; }
	int Quater[4] = { -1 , -1, -1, -1};
	std::vector<std::pair<int, int>> Point = { {0, 0}, {0, N / 2.}, {N / 2., 0},{N / 2., N / 2.} };
	std::vector<std::pair<int, int>> v = { {0, 0}, {0,0}, {0,0},{0,0} };
	for (int i = 0; i < N / 2; i++) {
		for (int j = 0; j < N / 2; j++) {
			for (int k = 0; k < 4; k++) {
				if (Arr[x + i + Point[k].first][y + j + Point[k].second] == 0) v[k].first++;
				else v[k].second++;
			}
		}
	}
	for (int i = 0; i < 4; i++) {
		if (v[i].first == N * N / 4) Quater[i] = 0;
		if (v[i].second == N * N / 4) Quater[i] = 1;
	}
	
	if (Quater[0] == 0 and  Quater[1] == 0 and Quater[2] == 0 and Quater[3] == 0) { printf("0"); return; }
	if (Quater[0] == 1 and  Quater[1] == 1 and Quater[2] == 1 and Quater[3] == 1) { printf("1"); return; }
	printf("(");
	for (int i = 0; i < 4; i++) {
		if (Quater[i] == 0) printf("0");
		else if (Quater[i] == 1) printf("1");
		else {
			QuadTree(Arr, N / 2, x + Point[i].first, y + Point[i].second);
		}
	}
	printf(")");
}

int main() {
	int N; scanf("%d", &N);
	int Arr[64][64]; char temp1, temp2;
	for (int i = 0; i < N; i++) {
		scanf("%c", &temp1);
		for (int j = 0; j < N; j++) {
			scanf("%c", &temp2);
			Arr[i][j] = temp2 - '0';
		}
	}
	
	QuadTree(Arr, N, 0, 0);
	return 0;
}

 

그리고 다른 분들이 푼 풀이도 봤는데, 내가 너무 문제를 어렵게 푸나 싶다ㅠ

 

💫zlzlzb님의 코드를 보면 훨씬 아이디어가 단순한데, 

 

나로 치면 QuadTree(시작점 x좌표, 시작점 y좌표, 전체 길이)를 정의할 때

for(int i = x, i < x + N, i++){for(int j = b,j <b + N, j++){}}인 이중 for loop을 정의하고 

Arr[i][j]의 값이 Arr[x][y]의 값고 다르면 다시 4개의 QuadTree함수를 부르는 방식을 택한 것이다.

 

이렇게 하면 나처럼 0과 1의 갯수를 모두 확인하지 않고도 간단하게 풀 수 있다!!