분할 정복 알고리즘에 대해서, 수열의 빠른 합 문제

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

분할 정복

문제를 거의 같은 크기인 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 재귀적으로 계산하고, 각 문제의 답으로부터 전체 문제의 답을 계산한다.

 

문제를 더 이상 나눠지지 않는 매우 작은 단위 (기저 사례) 까지 나누고 (Divide), 나눠서 해결한 문제의 답을 원래 문제의 답으로 합친다. (Merge)

 

수열의 빠른 합을 구하는 과정을 분할 정복으로 생각해보자. fastSum(n) 은 1 부터 n (자연수) 까지의 합을 구하는 함수이다. 먼저, n 까지의 합을 구하는 과정을 거의 같은 크기의 부분 문제로 나눈다. n 까지의 합을 구하는 과정을 절반으로 나누었다.

 

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

 

절반의 앞 부분인 (1 + 2 + ... + n/2) 는 fastSum(n/2) 이므로 재귀적으로 해결할 수 있다. 뒷 부분인 ((n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2)) 를 재귀적으로 해결하기 위해 "1 부터 n 까지의 합" 형태로 표현할 수 있을지 생각해보자.

 

((n/2 + 1) + (n/2 + 2) + ... + (n/2 + n/2)) 에는 (n/2)이 (n/2)개 만큼 있고 나머지는 "1 부터 n/2 까지의 합" 으로 표현할 수 있다. 즉, fastSum(n/2) + (n/2) * (n/2) 로 표현 가능하다.

 

결국, fastSum(n) = fastSum(n/2) + fastSum(n/2) + (n/2) * (n/2) 이 된다.

 

int fastSum(int n){
    // 기저 사례, 1 까지 합산.
    if(n == 1) return 1;
    
    // 홀수 입력을 처리.
    if(n % 2 == 1) return fastSum(n - 1) + n;

	return 2 * fastSum(n / 2) + (n / 2) * (n / 2);
}