분할 정복 (p. 175)

분할 정복이란?#

주어진 문제를 둘 이상의 부분 문제로 나누어 각 문제에 대한 답을 재귀 함수로 구한 뒤, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산하는 알고리즘

일반적인 재귀호출과 다른점은, 일반적인 재귀 호출은 f(N) = x + f(N-1)의 느낌이라면, 분할정복은 f(N) = f(N/2) + f(N/2)의 느낌이다.

분할 정복 알고리즘은 3가지 구성 요소를 갖는다.#

1. divide 문제를 더 작은 문제로 나눈다
2. merge 나뉘어진 문제의 답을 통해 원래 문제의 답을 찾는 병합과정을 거친다
3. base case 더 이상 분할할 필요가 없는 가장 작은 문제

분할 정복을 적용하기 위해선, 문제는 다음과 같은 특성을 갖는다.#

• 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.#

행렬의 곱셈을 예로 생각해보면, matrix $A$가 있고, 이를 $(2m+1)$번 곱한다고 하자 $(m \in \mathbb{N}_0)$

아래 2가지 분할 방법중 어느 것이 더 빠른 방법일까?

1. $A^{2m+1}=A \cdot A^{2m}=A\cdot A^m\cdot A^m$
2. $A^{2m+1} = A^{m}\cdot A^{m+1}$

정답은 1번이다. 1번이 분할정복에 해당하고, 2번은 아래와 같이 하나씩 재귀로 처리하는 것과 똑같은 연산속도를 보인다.

$A^{2m+1}=A\cdot A^{2m}=A\cdot A \cdot A^{2m-1} = ...$

즉, 2번과 같이 절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 바로 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문이다. 이런 속성을 부분 문제가 중복된다(overlapping subproblems)고 하고, 이런 문제를 해결할 수 있는 알고리즘이 나중에 소개되는 DP(Dynamic Programming; 동적 계획법)와 같다.

대표적인 분할정복 알고리즘: Merge Sort와 Quick Sort#

같은 분할정복 알고리즘을 사용하지만, Merge Sort는 병합(merge)하는데 시간이 걸리고, Quick Sort는 분할(divide)하는데 시간이 걸린다.

Karatsuba Algorithm#

두 수의 곱셈을 빠르게 하는 알고리즘으로 분할정복을 이용한다.

일반적인 곱셈 알고리즘은 $O(N^2)$의 시간이 걸린다.

카라추바 알고리즘은 $O(N^{log_23})$의 시간이 걸린다.

카라추바 알고리즘의 원리는 아래와 같다.

256자리수인 a와 b를 곱할 때, 그냥 곱하지 말고 두 수를 아래와 같이 나눠보자.

$a=a_1\times 10^{128} + a_0$

$b=b_1 \times 10^{128} + b_0$

$a\times b$

$= (a_1 \cdot 10^{128}+a_0)\cdot(b_1 \cdot 10^{128} + b_0)$

$=(a_1\cdot b_1)\cdot 10^{256} + (a_1\cdot b_0+a_0 \cdot b_1)\cdot 10^{128} + (a_0 \cdot b_0)$

여기서 $a_1\cdot b_1$과 $a_0 \cdot b_0$를 구하고, 아래와 같은 식을 세워보면

$(a_1+a_0)\cdot (b_1+b_0) = a_1 \cdot b_1 + (a_1\cdot b_0+a_0 \cdot b_1) + a_0 \cdot b_0$

$\Rightarrow (a_1+a_0)\cdot (b_1+b_0) - a_1 \cdot b_1 - a_0 \cdot b_0 = (a_1\cdot b_0+a_0 \cdot b_1)$

즉, 4번의 곱셈을 3번의 곱셈으로 바꾼 셈이 된다.