분할 정복 (Divide & Conquer)

도입

 

분할 정복은 가장 유명한 알고리즘이다.

쉽게 생각해 "각개 격파"로 생각하면 된다.

 

분할 정복은 일반적인 재귀 호출과 다르게 문제를 같은 크기의 여러 조각을 만든다.

 

이런 분할 정복을 사용하는 알고리즘들은 세 가지 구성 요소를 책에서 소개하고 있다.

 

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

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

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

 

분할 정복을 이용하면 같은 작업을 더 빠르게 처리할 수 있다.

 

예제 : 수열의 합

 

• 일반적인 재귀 호출을 이용한 코드

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

 

• 분할 정복을 이용한 코드

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

 

위 분할 정복 코드를 부연 설명하자면,

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

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

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

= (n/2)^2 + 2 * fastSum(n/2) <단, n은 짝수>  이다.

 

시간 복잡도 분석

 

일반적인 재귀 호출을 이용한 경우 n번 함수 호출하는 것을 알 수 있다.

반면에 분할 정복을 이용하면 대락 n/2번 호출하는 것을 알 수 있다.