분할정복(Divide-and-conquer)

 

*본 포스팅은 Algorithms(Sanjoy Dasgupta 외) 책을 정리한 것임*

[ 정의 ]

다음과 같은 방법으로 문제를 푸는 알고리즘을 분할정복이라 한다.

1. 문제를 동일한 타입의 더 작은 부분문제로 쪼갠다. (Breaking it into subproblems that are themselves smaller instances of the same type of problem.) 2. 부분문제들을 재귀적(순환적)으로 푼다.(Recursively solving these subproblems.) 3. 부분문제들을 푼 답을 적절하게 결합한다.(Appropriately combining their answers.)

실제적으로 문제의 해결은 전 단계(문제를 부분문제로 쪼개고-> 가장 작은 단위로 쪼개진(=아래 그림에서는 size 1) 부분문제를 해결하고 -> 찾은 부분 문제의 답을 결합하는 모든 과정)에서 조금씩 수행된다.

이를 recursion tree로 나타내면 다음과 같다.

크기 n 인 문제는 크기 n/b인 a개의 부분분제들로 쪼개어진다.

해결하고자 하는 크기 $n$인 문제는 나눌 때마다 $a$개의 크기 $n/b$인 부분문제들로 쪼개어진다.

단순히 재귀호출을 하는 것만으로 분할정복이라고 할 수 없다.

분할정복으로 풀 수 있는 문제란 부분문제로 나누었을 때 그 크기가 충분히 작아지는(=$b$가 충분히 큰) 문제를 의미하며, 이 때 쪼개어진 부분문제들은 서로 중복이 없어야 한다.

( ★ 예를 들어, 크기 $n$ 인 문제의 부분문제가 크기 $n-1$ / $n-2$ /...인 부분문제들로 정의되는 경우, 즉, 부분문제의 크기가 원래 문제에 비해 크게 줄어들지 않는 경우에는 분할정복으로 문제를 해결할 수 없다. 이 경우에는 Dynamic Programming을 활용)

 

[Running Time(시간복잡도)]

Master Theorem

크기 $ n $인 문제를 재귀적으로 풀 때, 그 부분문제가 크기 $ n/b $ 인 $ a $개의 부분문제들로 나누어지고,

부분문제들의 답을 결합하는 데에 걸리는 시간을 $ O(n^d) $라고 하자. (단, $ a, b > 0 , d \geqslant  0 $ )

이 때, 문제를 푸는데 걸리는 시간(running time)은 $ T\left ( n \right ) = aT\left ( \lceil n/b \rceil \right ) + O(n^d) $ 로 표현될 수 있다.

만약 running time이 위와 같은 꼴로 표현될 수 있다면, $ T(n) $ 은 $ a, b, d $ 의 크기에 따라 다음과 같이 계산될 수 있다. 

[증명] 증명의 편의를 위해서 $n$을 $b$의 배수라고 해보자. 이 가정은 증명에 어떤 영향도 끼치지 않는다. 그러면 $k=\log_b n$ 일 때 base case($n=1$)에 도달하게 된다. 따라서, $\log_b n$이 recursion tree의 깊이가 된다. 

깊이가$ k $(k번째 재귀호출)라고 해보자. 깊이=$k$에서 원래 문제는 크기가 $ \frac{n}{b^k} $인 $ a^k $개의 부분 문제로 쪼개어진다. 따라서, 깊이 $ k $일 때 수행해야 하는 일의 양(total work)은 $ a^k \times O(\frac{n}{b^k})^d $ (=문제수x문제의크기) 로 표현될 수 있다.  이는 정리하면 $ O(n^d) \times ( \frac{a}{b^d})^k $와 같다.

따라서, $ \frac{a}{b^d} $의 비(ratio)에 따라 $ T(n) $이 결정되므로, $ T(n) $은 '그 비가 1보다 작은 경우', '1보다 큰 경우', '1과 같은 경우'로 나눠서 살펴볼 수 있다.