분할정복

 

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

 

분할 정복을 사용하는 알고리즘의 세 가지 구성요소

- 문제를 더 작은 문제로 분할하는 과정(divide)

- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

 

분할 정복을 적용해 문제를 해결하기 위해서는 

1. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 하며,

2. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

 

 

[예제] 수열의 빠른 합

1부터 n까지의 합을 구하는 분할 정복 알고리즘

//필수조건 : n은 자연수
//1+2+...+n을 반환한다.

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

 

시간 복잡도

n의 이진수 표현의 자릿수 + 첫 자리를 제외하고 나타나는 1의 개수. 두 값의 상한은 모두 logn 이므로 시간복잡도는 O(logN)

 

 

[예제] 행렬의 거듭제곱

 

A = n*n 크기의 행렬

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

행렬의 거듭제곱을 구하는 분할정복 알고리즘

//정방행렬을 포현하는 SquareMarix 클래스가 있다고 가정하자.
class SquareMatrix;

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

//A^m을 반환한다.
SquareMatrix pow(const SquareMatreix& A, int m) {
	if(m==0) return identity(A.size());
    if(m%2 > 0) return pow(A, m-1) * A;
    SquareMatrix half = pow(A, m/2);
    //A^m = (A^(m/2))*(A^(m/2))
    return half * half;
 }

 

[예제] merge sort와 quick sort

병합 정렬과 퀵 정렬은 모두 분할 정복 패러다임에 기반하여 만들어진 것들이다.

 

병함 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

반대로 퀵 정렬 알고리즘은 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽의 배열의 수보다 항상 작도록 배열을 분할한다. 이를 위해 퀵 정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정이다.

 

병합 정렬은 주어진 배열을 나누는데는 O(1) 시간이 소요되지만, 정렬한 배열들을 하나로 합치는데 O(n)의 시간이 걸린다. 반면 퀵 정렬은 분할에서 O(n)의 시간이 걸리지만, 별도의 병합 작업이 필요 없다.

 

병합 정렬과 퀵 정렬의 시간복잡도 (부분 문제가 절반에 가깝게 나누어 지는 경우) : O(NlogN)

 

 

 

[문제] 쿼드 트리 뒤집기

algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

string reverse(string::iterator& it) {
	char head = *it;
    ++it;
    if(head == 'b' || head == 'w')
    	return string (1,head)
    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);
    
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
 }

 

[문제] 울타리 잘라내기

algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

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

//h[left,right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환
int solve(int left, int right) {
	if(left == right) return h[left];
    
    int mid = (left + right)/2;
    int ret = max(solve(left, mid), solve(mid+1, right));
    
    //두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
    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;
}

 

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 - 구종만 저