[알고리즘] 분할 정복(Divide and Conquer)과 Master Theorem

 

 

 

 

 

🧐 분할 정복이 뭐예요?

 

일반적으로 어떠한 문제를 더 작은 문제로 분할하고, 분할한 문제들을 해결한 후 조합하여 큰 문제를 해결하는 알고리즘을 의미합니다.

 

과정을 나열하자면 다음과 같습니다.

 

 

1. 주어진 문제를 더 작은 문제(Subproblem)으로 나눕니다. 
이때 작아진 문제는 본질적으로 큰 문제와 동일하나 단지 입력(input)의 크기만 작아진 문제를 의미합니다.

2. 1번 과정에서 나눈 Subproblem 들을 재귀적으로(더 작은 문제로 나누며) 해결합니다.

3. 2번에서 해결한 Subproblem들의 답을 적절하게 조합하여, 기존 큰 문제의 답을 도출합니다.

 

1번의 과정은 Divide
2, 3번의 과정은 Conquer 과정에 해당합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 분할 정복의 일반적인 패턴

 

분할 정복은 일반적으로 다음과 같은 패턴을 가집니다.

 

 

 

기존 문제의 크기(입력 사이즈)를 $n$ 이라 두겠습니다.

 

1. 기존 문제를 크기가 $\frac{n}{b}$ 인 $a$ 개의 Subproblem으로 나눕니다. (재귀적으로)

2. 각각의 Subproblem 들을 해결한 후, 이를의 답을 적절하게 조합합니다.

 

이때 조합하는 방법에 따라 각기 다른 시간 복잡도를 가질 수 있습니다.

조합하는 방법을 n에 대한 함수로 표현한 것을 $f(n)$라 하겠습니다.

 

이러한 경우 $T(n)$ 이 문제를 해결하는 데 필요한 시간 복잡도를 나타낸다고 하면, 다음과 같은 재귀적인 관계식을 얻을 수 있습니다.

$$T(n) = a \cdot T(\frac{n}{b}) + f(n)$$

 

 

위와 같은 형식을 갖는 recurrence relation(재귀적 관계식)의 일반해를 빠르게 구할 수 있는 방법으로 Master Theorem이 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Master Theorem

저희는 Master Threorem의 특수한 경우에 대해서만 알아볼 것이고, 더 일반적인 경우가 궁금하다면 다음 사이트에서 직접 검색해 보시면 됩니당 :)

 

상수 $a>0$,  $b > 1$,  $d \geq 0$ 에 대하여, 다음 recurrence relation
$$T(n) = a \cdot T(\frac{n}{b}) + O (n^{d})$$ 
의 일반해 $T(n)$ 은 다음과 같습니다.

$$T(n) = \left\{\begin{matrix} O(n^{d}) & if\;\; d > log_b \; a \\ O(n^{d}\; log\;n) &if\;\; d = log_b \; a \\ O(n^{log_b \; a}) & if \;\; d < log_b \; a \\ \end{matrix}\right.$$

 

 

 

증명

 

아래 recurrence relation의 recursion tree를 통해 증명을 진행하도록 하겠습니다.

$$T(n) = a \cdot T(\frac{n}{b}) + O (n^{d})$$ 

 

트리의 각 노드에 해당하는 문제는 a개의 subprolbem으로 쪼개집니다. 

이때 문제의 크기는 $\frac{1}{b}$ 배 만큼 줄어듭니다.

 

즉 트리의 height는 $log_b \; n$ 이 됩니다. ( root 노드의 level = 0 )

 

또한 k번째 level의 노드의 수는 최대 $a^k$ 개이고, 각각의 노드에 해당하는 subproblem의 크기는 $\frac{n}{b^k}$ 가 됩니다.

 

 

(저처럼) 이해하기 어려우신 분들을 위해 그림과 함께 설명했습니다.

 

 

결국 위와 같은 등비수열의 summation으로 표현이 가능해지며,

이 결과는 공비(Common ration)인 $\frac{a}{b^{d}}$ 의 값에 따라 달라집니다.

 

 

 

 

위와 같이 증명이 완료되었습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Master Theorem 적용 예시

 

병합 정렬(merge sort)

병합 정렬의 경우 크기가 $n$ 인 기존 문제를 크기가 $\frac{n}{2}$ 인 2개의 subproblem으로 분할하여 해결합니다.

 

Master Threoem에 대입하자면 $a = 2, b = 2$ 가 됩니다.

$d$ 의 경우에는 subproblem을 조합하는 과정에서 발생하는 시간으로, 병합 정렬에서는 선형 탐색을 통해 조합되므로 $O(n)$ 의 시간이 소모됩니다.

 

즉 병합 정렬의 시간 복잡도는, $d = log_b \;a$ 이므로 $O(n \;log \;n)$ 이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 더 빠른 곱하기 알고리즘

이전 시간에 알아본 곱하기 알고리즘은 시간 복잡도가 $O(n^2)$ 이었습니다.

분할 정복 알고리즘을 곱하기에 적용하여 더 빠른 알고리즘을 알아보도록 하겠습니다.

 

 

 

n 비트 이진수의 곱셈을 예시로, 편의상 n은 2의 거듭제곱 형태라 가정하도록 하겠습니다.

 

곱하는 두 수는 $x$ 와 $y$ 이며, $x$ 의 왼쪽 $\frac{n}{2}$ 비트를 $x_L$ , 나머지 오른쪽 비트를 $x_R$ 이라 하고, 마찬가지로 $y$ 에 대해서도 동일하게 적용된다 하겠습니다.

 

예를 들어 다음과 같습니다.

 

이때 $x_L, x_R, y_L, y_R$의 정의에 따라 다음과 같습니다.

$$x = 2^{n/2} \cdot x_L + x_R$$

$$y = 2^{n/2} \cdot y_L + y_R$$

 

 

이제 두 수를 곱해보도록 하겠습니다.

 

즉 위 식의 결과에 따라 $x$ 와 $y$ 를 곱하는 문제는

 

1. 두 $\frac{n}{2}$ 비트 이진수를 곱하는 4개의 subproblem과

2. 이들에 대하여 $2^n$ 과 $2^{\frac{n}{2}}$ 를 곱하는, 즉 $n + \frac{n}{2}$ 만큼의 Shift 연산과

3. 3번의 덧셈 과정으로 나뉘어집니다.

 

 

즉 두 n비트 이진수 x와 y를 곱하는 데 걸리는 시간을 $T(n)$ 이라 하면, 다음이 성립합니다.

$$T(n) = 4 T(\frac{n}{2}) + O(n)$$

 

 

결국 $1 < log_2 \;4  = 2$ 이므로, Master Theorem에 의하여 $T(n) = O(n^2)$ 이 됩니다.

 

결론적으로 성능 향상은 없었습니다만, 이 식에 하나의 트릭을 사용하여 성능을 높일 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Gauss's Trick

 

다음 수식을 사용합니다.

 

 

 

위 식으로 도출된 결과를 기존 식에 대입하면 아래와 같습니다.

 

 

즉 기존 4개의 subproblem으로 나뉘었던 곱셈이,

Gauss's Trick을 사용하여 3개의 $\frac{n}{2}$ 비트 이진수를 곱하는 subproblem으로 나뉠 수 있다는 것을 알게 되었습니다.

 

이때 3개의 subproblem은 각각 다음과 같습니다.

$$(x_L + x_R) \cdot (y_L + y_R)$$

$$x_L \cdot y_L$$

$$x_R \cdot y_R$$

 

 

 

 

 여기서 잠깐 👀

$(x_L + x_R) \cdot (y_L + y_R)$에서 두 수의 덧셈은 최대 $\frac{n}{2} + 1$ 비트가 될 수 있지만, 이는 무시 가능합니다.

 

 

 

 

결국 위 곱셉의 시간 복잡도는 다음과 같은 recurrence relation을 도출합니다.

$$T(n) = 3T(\frac{n}{2}) + O(n)$$

 

이는 Master Theorem에 따라 다음과 같은 시간 복잡도를 가집니다.

$$T(n) = O(n^{log_2 3}) \approx  O(n^{1.59x})$$