[C++ 알고리즘] 분할정복(Divide and conquer)

개념

분할정복 알고리즘은 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘이다. 종만북의 표현을 빌리자면 각개 격파 라고 간단히 설명할 수 있다.

 

바로 예제를 보도록 하자.

 

예제 1 : 수열의 합

1부터 N까지의 값을 구해야 한다고 가정하자. 이를 단순 재귀함수로 구현하면 아래와 같을 것이다.

#include <iostream>
using namespace std;

int recursiveSum(int N) {
	if (N == 1) {
		return N;
	}
	else {
		return recursiveSum(N - 1) + N;
	}
}

int main() {
	int A;
	cin >> A;
	cout << recursiveSum(A);
}

재귀함수로 함수를 짜면 굉장히 직관적이지만 위 함수의 경우 시간이 오래 걸린다. 또 5000정도의 숫자부터는 프로그램이 죽어버린다.

아무것도 출력되지 않는다.

 

그렇다면 다른 방법으로 프로그램을 짜보자. 1+2+3+4+...+N이라는 식을 살짝 변형해서 분할정복을 하기 좋게 바꿀 것이다. 아래 식을 보도록 하자.

1+2+3+4+5+6+7+8
=(1+2+3+4)+(5+6+7+8)
=(1+2+3+4)+4*4+(1+2+3+4)
=2*(1+2+3+4)+4^2

이제 위 식을 같은 방식으로 일반화 해보면 아래와 같다.

1+2+3+4+...N
=(1+2+3+4+...+N/2)+{(N/2+1)+(N/2+2)+(N/2+3)+...+(N/2+N/2)}
=(1+2+3+4+...+N/2)+{(N/2)*(N-2)}+(1+2+3+4+...+N/2)
=2*(1+2+3+4+...+N/2)+(N/2)^2

문제를 보면 1+2+3+4+...N을 구하는 문제가 1+2+3+...+N/2로 바뀌었음을 알 수 있다. 이것이 분할정복의 핵심이다. 그렇다면 1+2+3+...+N/2를 또 쪼개면 1+2+3+...+N/4라는 문제가 나오고, 계속해서 쪼개나가면 문제를 점점 작은 조각으로 자를 수 있다. 물론 위 식은 짝수일 경우만 적용된다. 홀수일 경우에는 N-1까지의 합을 구하고 N을 더하는 식으로 수열의 합을 구한다.

 

위 과정을 코드로 짜면 아래와 같다.

 

#include <iostream> 
using namespace std;

int fastsum(int x) {
	if (x == 1) {
		return x;
	}
	else {
		if (x % 2 == 0) {
			return fastsum(x / 2) * 2 + (x / 2)*(x/2);
		}
		else {
			return fastsum((x - 1) / 2) * 2 + ((x - 1) / 2)* ((x - 1) / 2) + x;
		}
	}
}

int main() {
	int A;
	cin >> A;
	cout << fastsum(A);
}

이제 큰 수를 넣어도 프로그램이 죽지 않는다. 즉 두 번째 코드가 더 효율적임을 알 수 있다.

5000을 넣어도 프로그램이 죽지 않는다.

 

예제 2 : 병합정렬(Merge Sort)

이제 분할정복의 대표적인 예시인 병합정렬에 대해 알아보자. 병합 정렬의 과정은 아래와 같다.

1. 2개씩 묶일 때 까지 반으로 쪼개나간다.
2. 각 요소들을 정렬하며 합쳐나간다.(두 묶음이 될 때 까지)
3. 2에서 나온 두 묶음에서 맨 앞을 비교해 크기가 작은 요소를 가져와 배치한다.

아래 그림을 보도록 하자.

분할과정

병합과정

 

분할과정을 수행할 때에는 각 덩어리의 맨 앞을 비교해 더 작은 값을 가져와 합쳐나가야 한다.

병합과정 상세

 

이제 위 과정을 코드로 짜 보도록 하자.

#include<iostream>

using namespace std;

int arr[10];
int arr2[10];

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j])
			arr2[k++] = arr[i++];
		else
			arr2[k++] = arr[j++];
	}

	int tmp = i > mid ? j : i;

	while (k <= right) arr2[k++] = arr[tmp++];

	for (int i = left; i <= right; i++) arr[i] = arr2[i];
}

void divide(int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		divide(left, mid);
		divide(mid + 1, right);
		merge(left, right);
	}
}

int main() {
	int a;
	for (int i = 0; i < 10; i++) {
		cin >> a;
		arr[i] = a;
	}
	

	divide(0, 9);

	for (int i = 0; i < 10; i++) {
		cout << arr2[i] << " ";
	}

	
}

 

10개의 수를 받아 arr배열에 넣어 분할 정렬한 뒤 arr2배열에 값을 넣어주는 코드이다.

 

---

이 문제는 처음 볼 때는 생소할 수 있지만, 이 문제를 통해 분할정복을 어떻게 적용하는지 학습하고 다음 문제를 풀어나가면 좋을 것 같다.

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

2630번: 색종이 만들기

 

 

앞 단계와 똑같이 풀 수 있는 문제이다. 경우의 수가 조금 늘어난다. 앞 문제를 이해했다면 무리없이 풀 수 있다.

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

1780번: 종이의 개수

 

 

앞 문제의 응용판같은 문제이다. 문제 풀이 방식을 조금 바꿔야 한다. 시간 제한에 걸리지 않고 해결할 방법을 생각하며 풀어보도록 하자.

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

1074번: Z