분할정복(Divide & Conquer)알고리즘은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산해 낸다. 분할 정복의 장점은 많은 경우 같은 작업을 더 빠르게 처리해 준다.

분할 정복의 구성요소

• Divide : 더 작은 문제로 나눈다.
• Merge : 나눈 문제에서 구한 답을 병합해 원래 답을 구한다.
• Base Case: 더 이상 분할 하지 않고, 곧장 풀 수 있는 문제.

예제: 수열의 빠른 합

1부터 n까지의 합을 n개의 조각으로 나눈뒤, 이들을 반으로 잘라 n/2개의 조각들로 만들어진 부분 문제를 두개 만든다. (편의상 n이 짝수라고 가정)

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

첫번째 문제는 fastSum(n/2) 로 나타낼 수 있지만, 두번째 부분 문제는 그렇지 않다. 문제를 재귀적으로 풀기 위해서는 각 부분 문제를 1부터 n까지의 합 꼴로 표현해야 한다. 따라서 두번째 부분 문제를 fastSum(x)를 포함하는 형태로 바꿔준다.

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

이러한 아이디어를 코드로 구현하면 아래와 같다. 만약 n이 홀수인 경우에는 짝수인 n-1까지의 합을 재귀 호출로 계산하고 n을 더해 답을 구하면 된다.

// 1+2+...+n을 반환
const fastSum = (n:number):number => {
    if(n === 1) return 1; // Base Case
    if(n % 2) return fastSum(n-1) + n; // n이 홀수인 경우
    return 2 * fastSum(n/2) + (n/2)*(n/2);
}

시간복잡도 분석

fastSum()은 호출될 때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다. 이 알고리즘의 실행시간은 O(logn)이다.