분할 정복

분할 정복(Divede & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라느 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해낸다.

 

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

 

분할 정복을 적용해 문제를 해결하기 위해서는 문제에 몇가지 특성이 성립해야한다.

① 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.

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

 

분할 정복은 많은 경우 같은 작업을 더 빠르게 처리할 수 있다.

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

일반적인 재귀 호출 함수로 수열의 합을 구하려 한다면,

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

가 되며, 총 n번의 호출이 필요해 시간복잡도가 O(n)이 된다. 이걸 분할정복을 이용한다면 빠르게 해결이 가능하다

 

fastSum( ) = 1+ 2 + ,,, + n

              = (1 + 2 + ,,, + n / 2) + ((n/2+1) + ,,, + n)

              = n / 2 * n / 2 + (1 + 2 + 3 + ,,, + n / 2)

              = n / 2 * n / 2 + fastSum(n/2)

-> fastSum(n) = 2 * fastSum(n/2) + n^2 / 4 (n이 짝수일 때)

 

< 1부터 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);
}

위 분할정복 알고리즘은 O(logN)이 된다.