7장. 분할 정복

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다.

7.1 도입

분할 정복(Divede & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것에 있다.

 

분할 정복 알고리즘은 다음과 같은 세 가지 구성 요소를 가지고 있다.

1. Divide : 문제를 더 작은 문제로 분할하는 과정
2. Merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
3. Base Case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

따라서 분할 정복은 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 분할 정복은 많은 경우 같은 작업을 더 빠르게 처리해 주는 장점을 가지고 있다.

 

예제 : 수열의 빠른 합과 행렬의 빠른 곱

수열의 빠른 합

fastSum( n ) = 1 + 2 + 3 + .... + n =(1 + 2 + ... (n/2)) + ((n/2+1) + (n/2+2) .... + n )

                 = (1 + 2 + ... (n/2)) + ((n/2+1) + (n/2 +2) + (n/2 + 3) .... ((n/2+n/2))

                 = fastSum(n/2) + (n/2)*(n/2)+(1 + 2 + 3 ... n/2 )

                 = fastSum(n/2) + fastSum(n/2) + (n^2)/4

// 분할 정복을 이용하여 1+2+3 ... +n을 계산하는 알고리즘
int fastSum(int n) {
	//base case
	if (n == 1) return 1;

	if (n % 2 == 1) return fastSum(n - 1) + n;
	else return 2 * (fastSum(n / 2)) + (n*n) / 4;
}

 

6장에서 살펴봤던 일반적인 재귀 호출을 이용한 recursiveSum( )과 시간 복잡도를 분석해보면 recursiveSum( )은 n번의 함수 호출이 필요하지만 fastSum( )은 호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어드니 fastSum( )의 호출 횟수가 훨씬 적으리란 것을 쉽게 예상할 수 있다.

recursiveSum ( ) 의 시간복잡도 : O(N)

fastSum ( )의 시간복잡도 : O(logN)

 

행렬의 빠른 곱

n x n 크기의 행렬 A가 주어질 때, A의 거듭제곱 A^m은 A를 연속해서 m번 곱한 것이다. 이것을 계산하는 알고리즘 자체는 어려울 것이 없지만, m이 매우 클 때 꽤나 시간이 오래 걸리는 작업이다. 행렬의 곱셈에는 O(n^3)의 시간이 들기 때문에 곧이곧대로 m-1번의 곱셈을 통해 A^m을 구하려면 모두 O(n^3 * m)번의 연산이 필요하다.

하지만 분할 정복을 이용하면 휠씬 더 개선된 연산 속도로 알고리즘을 구현 할 수 있다.

 

A^m = A^(m/2) * A^(m/2)

 

//정방행렬을 표현하는 SquareMatrix Class
class SquareMatrix;

//n*n 크기의 항등행렬(identity matrix)를 반환하는 함수
SquareMatrix identity(int n);

// A^m을 반환하는 함수
SquareMatrix pow(const SquareMatrix& A, int m) {
	//base case : A^0 = I
	if (m == 0) return identity(m);

	//m이 홀수인 경우 처리
	if (m % 2 > 0) return pow(A, m - 1);

	SquareMatrix half = pow(A, m / 2);

	return half * half;
}

 

예제 : 병합 정렬과 퀵 정렬

주어진 수열을 크기 순서대로 정렬하는 문제는 전산학에서 가장 유명한 문제이다. 이 문제를 해결하는 수 많은 알고리즘 중 가장 널리 쓰이는 것이 바로 병합 정렬(Merge Sort)와 퀵 정렬(Quick Sort)인데, 이 두 알고리즘은 모두 분할 정복 패러다임을 기반으로 만들어졌다. 

병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다. 반대로 퀵 정렬 알고리즘은 배열을 단순하게 가운데에서 쪼개는 대신 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 퀵 정렬은 partition이라고 부르는 단계를 도입하는데 이는 배열에 있는 수 중 임의의 기준 수(Pivot)을 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.

병합 정렬의 경우 최선, 최악의 경우 모두 O(NlogN) 의 시간 복잡도를 갖게 되고, 퀵 정렬의 경우 최악의 경우 O(n^2)의 시간 복잡도를 갖지만 평균적으로 O(NlogN)의 시간 복잡도를 갖는다. 또한 병합 정렬은 안정정렬인 반면 퀵 정렬은 불안정 정렬이란 차이도 가지고 있다.

 

병합정렬, 퀵정렬 알고리즘 소스코드 출처 : https://dpdpwl.tistory.com/

#include<iostream>

using namespace std;

int N,arr[1000001];
int *arr2;

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 partition(int left,int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; 
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

int main()
{
	scanf("%d",&N);
	arr2 = new int[N];
	for (int i=0;i<N;i++) scanf("%d",&arr[i]);

	partition(0, N - 1);

	for (int i=0;i<N;i++) printf("%d\n",arr[i]) ;
}

#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];

void quickSort(int i, int j)
{
	if(i>=j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++;
		while(quick[right]>pivot) right--;
		if(left<=right)
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}

int main() 
{
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&quick[i]);

	quickSort(0,n-1);

	for(int j = 0; j < n; j++) // 출력
		printf("%d\n",quick[j]);
}

 

예제 : 카라츠바의 빠른 곱셈 알고리즘 

 

카라츠바의 빠른 곱셈 알고리즘은 두 개의 정수를 곱하는 알고리즘이다. 수백자리, 나아가 수만 자리의 큰 숫자들을 다룰 때 주로 사용된다. 이렇게 큰 숫자들은 배열을 이용해 저장해야 한다. 두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 초등학교 산수 시간에 배운 방법을 그대로 사용하는 것이다. 하지만 이는 O(n^2)의 시간복잡도를 갖게 된다. 하지만 카라츠바 알고리즘은 분할 정복을 이용하여 이보다 더 빠른 계산을 가능하게 해준다.

 카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다. 가령, a와 b가 256자리 수라면 a1과 b1은 첫 128자리, a0 와 b0는 그 다음 128자리를 저장하도록 하는 것이다. 이런 방법의 분할은 큰 정수 두개를 한 번 곱하는 대신 절반 크기로 나눈 작은 조각을 네 번 곱하게 된다. 이때 절반인 조각을 네 번 곱한다면 일반적인 곱셈 알고리즘과  같은 O(n^2)의 시간 복잡성을 갖게 된다. 하지만 카르바츠는 크기를 절반으로 나누어 곱하면 4번 곱하는 것이 아닌 3번의 곱셈으로만 이 값을 계산 할 수 있다는 것에 집중하였다. 이러한 방법으로 O(n^(log3))의 복잡도를 갖는 큰 수 곱셈 알고리즘을 구현 할 수 있게 되었다.

 

a = a1 x 10^128 + a0

b = b1 x 10^128 + b0

 

a x b = (a1 x 10^128 + a0) x (b1 x 10^128 + b0)

        = a1 x b1 x 10^256 + (a1 x b0 + a0 x b1) x 10^128 + a0 x b0       <- 네 부분이 아닌 세 부분으로 분할!

 

TIP : 10의 거듭제곱과 곱하는 것은 그냥 뒤에 0을 붙이는 시프트 연산으로 구현하면 되니 곱셈으로 치지 않는다!

 

//카라츠바의 빠른 정수 곱셈 알고리즘

#include <vector>

//a += b*(10^k)을 계산하는 함수
void addTo(vector<int>& a, const vector<int>&b, int k);

// a-=b를 계산하는 함수 (a>=b를 가정)
void subFrom(vector<int>&a, const vector<int>& b);

//두 긴 정수의 곱을 반환한다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
	int an = a.size(), bn = b.size();

	//a가 b보다 짧을 경우 둘을 바꾼다.
	if (an < bn) return karatsuba(b, a);

	//error case : a or b가 비어있는 경우
	if(an==0 || bn ==0) return vector<int>();

	//a와 b를 밑에서 half 자리와 나머지로 분리한다.
	int half = an / 2;

	//분할 정복
	vector<int> a0 = (a.begin(), a.begin() + half), a1 = (a.begin() + half, a.end());
	vector<int> b0 = (b.begin(), min<int>(b.size(), half)), b1 = (min<int>(b.size(), half), b.end());

	//z2 = a1 * b1
	vector<int> z2 = karatsuba(a1, b1);
	//z0 = a0 * b0
	vector<int> z0 = karatsuba(a0, b0);

	//a0 = a0 + a1, b0 = b0 + b1
	addTo(a0, a1, 0); addTo(b0, b1, 0);
	//z1=(a0 * b0) -z0 -z1
	vector<int> z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//ret=z0 + z1*10^half + z2*10^(half*2)
	vector<int> ret;
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half * 2);

	return ret;
}

 

---

7.2 문제 : 쿼드 트리 뒤집기

https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

이 문제를 풀 수 있는 가장 무식한 방법은 주어진 그림의 퀴드 트리 압출을 풀어서 실제 이미지를 얻고, 상하 반전한 뒤 다시 퀴드 트리 압축하는 것입니다. 물론 문제에 주어진 원본 그림의 크기 제한을 보면 이 방법을 곧이곧대로 구현 할 수 없다는 것을 알 수 있습니다. 이런 경우 대개 우리가 선택할 수 있는 접근 방법은 두 가지 입니다.

• 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
• 작은 입력에 대해서만 작동하는 단순한 알고리즘으로부터 시작해서 최적화해 나가기

둘 중 어느 접근이 맞는지 판단하기란 쉽지 않으며 시행착오와 경험이 필요하다. 그러나 둘 중 확실히 더 쉬운 것은 단순한 알고리즘에서 시작해서 최적화해 나가는 것이다. 그러니 우선 그림의 크기에 신경 쓰지 않고 퀘드 트리의 압축을 어떻게 풀어야 할지에 대해 알아보자.

 

쿼드 트리 압축 풀기

쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀호출로 구현하는 것이 가장 자연스럽다. 문자열 s의 압축을 해제해서 N x N 크기의 배열에 저장하는 함수 decompress( )를 구현한다고 하자. base case는 s의 첫글자가 w나 b인 경우이고 이때는 배열 전체에 해당 색을 칠하고 종료한다. 만역 첫 글자가 x라면 decompress( )는 s의 나머지 부분을 넷으로 쪼개 재귀 호출한다. 

 이렇게 생각하고 곧장 구현을 시작하면 s의 나머지 부분의 길이가 일정하지 않기 때문에 네 부분으로 쪼개기가 까다롭단 사실을 알게 된다. 이를 해결하기 위해 생각할 수 있는 첫 번째 방법은 주어진 위치에서 시작하는 압축결과의 길이를 반환하는 함수 getChunkLength( )를 만드는 것이다. s[0]가 x라고 하면, 왼쪽 위 조각을 나타내는 부분은 항상 s[1]에서부터 시작한다. 이때 getChunkLength(s, 1)이 해당 부분 압축의 길이를 반환하도록 하는 것이다. getChunkLength(s, 1)이 5를 반환하면 다음 조각은 s[6]부터 시작한다는 것을 알 수 있다.  getChunckLength( )를 재귀 호출로 작성하는 것은 어렵지 않지만 비슷한 일을 하는 두 개의 함수를 각각 작성한다는 점에서 비효율적이다.

 이럴 때 유용하게 써먹을 수 있는 패턴은 s를 미리 쪼개는 것이 아니라 decompress( )함수에서 필요한 만큼 가져다 쓰도록 하는 것입니다. s를 통째로 전달하는 것이 아니라, s의 한 글자를 가리키는 포인터를 전달합니다. 함수 내에서는 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮깁니다.

 

#define MAX_SIZE 20
#include<string>

char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(string::iterator& it, int y, int x, int size) {
	//한 글자를 검사할 때마다 반복자를 한칸씩 앞으로 옮긴다.
	char head = *(it++);

	if (head == 'b' || head == 'w') {
		for (int dy = 0; dy < size; dy++) {
			for (int dx = 0; dx < size; dx++) {
				decompressed[y + dy][x + dx] = head;
			}
		}
	}
	else {
		//네 부분을 각각 순서대로 압축 해제한다.
		int half = size / 2;
		decompress(it, y, x, half);
		decompress(it, y, x+half, half);
		decompress(it, y+half, x, half);
		decompress(it, y+half, x+half, half);
	}
}

 

압축 다 풀지 않고 뒤집기

 주어진 원본의 크기는 2^20 x 2^20 이기 때문에 압축해제를 해서 메모리 올려 처리하기는 무리가 있다. 압축을 해제하지 않고 이미지를 뒤집는 결과를 곧장 생성하는 코드를 작성 할 필요가 있다. 

 base case를 생각해보면 전체가 검은 색이나 흰색인 그림은 뒤집어 봤자 다를게 없다. 뒤집은 결과가 원래 그림과 똑같기 때문이다. 전체가 한 가지 색이 아닌 경우에는 재귀 호출을 이용해 네 부분을 각각 상하로 뒤집은 결과를 얻은 뒤, 이들을 병합해 답을 얻어야 합니다. 그렇다면 뒤집힌 그림의 압축 결과가 이미 존재한다면 이들을 어떻게 병합할 것인가?

이 때 사등분 된 각 조각들은 상하반전이 되어 있기 때문에 사등분중 위 두조각과 아래 두조각의 위치를 바꿔준다면 전체 그림의 상하 반전이 이루어지게 된다.

 

#include<string>

string reverse(string::iterator& it) {
	char head = *it;
	it++;
	
	//base case
	if (head == 'b' || head == 'w') return string(1, head);

	string upperLight = reverse(it);
	string upperRight = reverse(it);
	string lowerLight = reverse(it);
	string lowerRight = reverse(it);

	//위 두 조각과 아래 두조각의 위치를 바꾼다.
	return string("x") + loweLeft + lowerRight + upperLeft + upperRight;
}

 

---

7.3 문제 : 울타리 잘라내기

https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

무식하게 풀 수 있을까? (완전 정복)

각 판자 높이의 배열 h[]가 주어졌을 때 l번 판자부터 r번 판자까지 잘라내서 사각형을 만든다고 합시다. 이때 사각형의 넓이는 (r-l+1)*min(h[i])가 되는데 min(h[i])를 구하기 위해선 l과 r을 순회하는 이중 loop를 계산해야 된다. 이중 loop를 계산하기 위해선 O(n^2)의 시간복잡도가 걸리기 때문에 제한 시간 안에 최대 크기 20000의 input을 계산하는 것에는 무리가 있어보인다.

#include <vector>

//판자의 높이를 담은 배열 h[]가 주어질 때 사각형의 최대 너비를 반환한다.
int bruteForce(const vector<int>& h) {
	int ret = 0;
	int N = h.size();

	//가능한 모든 left, right 조합을 순회한다.
	for (int left = 0; left < N; left++) {
		for (int right = 0; right < N; right++) {
			minHeight = min(minHeight, h[right]);
			ret = max(ret, (right - left)*minHeifgt);
		}
	}

	return ret;
}

 

분할 정복 알고리즘 설계

분할 정복 알고리즘을 설계하기 위해서는 문제를 어떻게 분할할지를 가장 먼저 결정해야 한다. n개의 판자를 절반으로 나눠 두 개의 부분 문제를 만든다. 그러면 우리가 찾는 최대 직사각형의 넓이는 다음 세 가지 중 하나에 속한다.

• 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐있다.

이 때 첫 번째와 두 번째 경우는 반으로 나눈 부분 문제를 재귀 호출하여 해결 할 수 있다. 세 번째 경우 답을 빠르게 구할 수만 있으면 분할 정복 알고리즘이 완성된다!

 

양쪽 부분 문제에 걸친 경우의 답

양쪽 부분 문제에 모두 걸치는 직사각형을 찾는 방법은 반드시 부분 문제 경계에 있는 두 판자를 포함한다는 것에 있다. 가운데 직사각형에서 시작하여 왼쪽과 오른쪽 각각 한 칸씩 확대해나간다고 할때 반드시 넓이가 넓어지는 방향으로 확장해나가야 한다. 이를 이용하여 세 번째 부분문제를 해결 할 수 있다.

 

#include<vector>

//각 판자의 높이를 저장하는 배열
vector<int> h;

//h[left,right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {

	//base case
	if (left == right) return h[left];

	int mid = (left + right) / 2;
	
	// 부분문제 1,2 : 왼쪽 혹은 오른쪽 조각에 가장 큰 사각형이 있는 경우
	int ret = max(solve(left, mid), solve(mid + 1, right);

	//부분문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
	int lo = mid, hi = mid + 1;
	int height = min(h[lo], h[hi]);

	//[mid,mid+1]만 포함하는 너비 2인 사각형을 고려한다.
	ret = max(ret, height * 2);

	//사각형이 입력 전체를 덮을 때까지 확장해 나간다.
	while (left < lo || hi < right) {
		//항상 높이가 더 높은 쪽 (넓이가 더 넓어지는 쪽)으로 확장한다.
		if (hi < right && (lo == left || h[lo - 1] < h[hi + 1]) {
			hi++;
			height=min(height,h[hi);
		}
		else {
			lo--;
			height=min(height,h[lo]);
		}

		//확장 후 사각형의 넓이
		ret=max(ret, height * (hi-lo+1));
	}

	return ret;
}

---

7.4 문제 : 팬미팅 

https://algospot.com/judge/problem/read/FANMEETING

algospot.com :: FANMEETING

이 문제를 푸는 가장 단순한 방법은 문제에 나와있는 팬미팅 과정을 시뮬레이션 하는 것입니다. 하지만 멤버의 수와 팬의 수가 모두 200,000까지 가능함으로 정해진 시간 안에 풀기 어렵다는 사실을 알 수 있습니다.

 

곱셈으로 변형

이 문제를 푸는 방법은 놀랍게도 두 큰수의 곱셈으로 이 문제를 바꾸는 것입니다. 길이가 N인 정수A와 길이가 M인 정수B를 곱한 결과를 C라하고 각 숫자의 i번째 자리수를 Ai, Bi, Ci라고 합시다. 

이때 산술연산을 살펴보며(다항정리와 유사) Ci= Ai*B0 + A(i-1)*B1 + A(i-2)*B2 ... A0*Bi가 됨을 알 수 있습니다.

이 사실을 이용하여 문제를 해결 할 수 있습니다. 일렬로 선 사람들의 성별을 긴 정수로 표현합시다. 각 자릿수는 한 사람의 성별을 나타내며 남성은 1, 여성은 0으로 표시하지요. 그러면 남성과 남성이 만났을 때 두 자릿수의 곱셈은 1이 됩니다. 이 외의 경우에는 두 자리수의 곱셈이 항상 0이 됨을 알 수 있습니다. 따라서 자리 올림을 생략했을 때 Ci가 0이라면 해당 위치에서 남성팬과 남성 맴버가 만나는 일이 없고 따라서 모든 맴버가 포옹한다는 것을 알 수 있다.

 

카라츠바 알고리즘을 이용한 구현

앞서 살펴봤던 카라츠바의 빠른 정수곱셈 알고리즘을 응용하면 해당 문제를 빠르게 해결 할 수 있다.

#include <string>
#include <vector>

extern vector<int> karasuba(vector<int> a, vector<int> b);

int hugs(const string& mambers, const string& fans) {
	int N = members.size(), M = fans.size();
	vector<int> A(N), B(N);

	for (int i = 0; i < N; i++) {
		A[i] = (members[i] == 'M');
	}

	for (int i = 0; i < M; i++) {
		//A와 순서를 거꾸로!
		B[M - i - 1] = (fans[i] == 'M');
	}

	//Karasuba 알고리즘에서 자리 올림을 수행하지 않게 변형한다.
	vector<int> C = karasuba(a, b);
	int allHug = 0;
	for (int i = N - 1; i < M; i++) {
		if (C[i] == 0) allHug++;
	}

	return allHug;

}