0x03. 분할 정복과 점화식

분할 정복(Divide and Conquer) 알고리즘은 문제를 작은 부분 문제로 쪼개고, 각각을 재귀적으로 풀어 합치는 방식이다. 이때 알고리즘의 시간 복잡도는 점화식(Recurrence) 으로 표현되는데, 이 점화식을 풀어야 비로소 알고리즘이 얼마나 효율적인지 알 수 있다.

이 글에서는 점화식이 무엇인지 살펴보고, 이를 풀기 위한 네 가지 방법 -- 치환법, 재귀 트리, 반복법, 마스터 정리 -- 을 정리한다. 마지막으로 수학적 귀납법을 이용한 증명과 다양한 연습 문제를 다룬다.

점화식(Recurrence)이란?

점화식(Recurrence) 이란, 함수의 값을 더 작은 입력에 대한 함수 값으로 표현하는 방정식이다. 예를 들어 Merge Sort의 시간 복잡도 $T(n) = 2T(n/2) + \Theta(n)$이 대표적인 점화식이다.

분할 정복 알고리즘을 분석하려면 이 점화식을 닫힌 형태(Closed Form) 로 풀어야 한다. 즉, $T(n) = \Theta(n \log n)$처럼 $n$에 대한 명시적 표현을 구하는 것이 목표다.

점화식 풀이 방법

1. 치환법 (Substitution Method)

치환법은 답을 먼저 추측한 뒤, 수학적 귀납법(Mathematical Induction) 으로 그 추측이 맞는지 증명하는 방법이다.

직관이나 경험을 바탕으로 상한(Upper Bound)이나 하한(Lower Bound)을 추측하고, 귀납법으로 검증한다. 추측이 틀리면 다른 형태로 다시 시도하면 된다. 개념은 단순하지만, 올바른 추측을 해내는 것이 핵심이다.

2. 재귀 트리 (Recursion-Tree Method)

재귀 트리 방법은 점화식을 트리 구조로 시각화하여 비용을 계산하는 방법이다. 절차는 다음과 같다.

1. 재귀 트리를 구성한다. 각 노드는 해당 부분 문제 하나의 비용을 나타낸다.
2. 각 레벨의 비용을 합산한다.
3. 모든 레벨의 비용을 합산하여 전체 비용을 구한다.

재귀 트리는 비용이 어디서 발생하는지 직관적으로 파악할 수 있어, 복잡한 점화식에서도 패턴을 찾기 좋다.

재귀 트리 예제

3. 반복법 (Iteration Method)

반복법은 점화식을 반복적으로 전개(expand) 하여 패턴을 찾아내는 방법이다.

예제

점화식을 반복 대입하면 다음과 같은 패턴이 보인다.

$n \geq k$일 때, $s(n) = ck + s(n-k)$ 가 성립한다.

여기서 $k = n$으로 놓으면:

$s(n) = cn + s(0) = cn$

따라서 일반적으로 $s(n) = cn = \Theta(n)$ 이 된다.

유사한 방법

4. 마스터 정리 (Master Method)

마스터 정리는 $T(n) = aT(n/b) + f(n)$ 형태의 점화식에 대해, $a$, $b$, $f(n)$의 관계만으로 바로 시간 복잡도를 결정하는 강력한 도구다. 복잡한 트리를 그리거나 귀납법을 사용할 필요 없이, 세 가지 케이스 중 어디에 해당하는지만 판별하면 된다.

마스터 정리 예제

수학적 귀납법 (Proof by Induction)

점화식 풀이에서 추측한 답이 맞는지 엄밀하게 증명하려면 수학적 귀납법을 사용한다. 구조는 다음과 같다.

Base case: $n = 0$ 또는 $n = 1$일 때 공식이 성립함을 보인다.

Inductive hypothesis: $n > 0$에 대해, **$k \geq 0$이고 k < n인 모든 $k$**에서 공식이 성립한다고 가정한다. 귀납 가정에 의해, $k = n - 1$ (또는 $k = n/2$)일 때 공식이 참이다.

Proof of goal statement: 위 가정 하에서 **$n$**일 때도 공식이 성립함을 보인다.

여기서 주의할 점이 있다. 흔히 다른 귀납법에서 "n+1일 때 성립함을 보인다"라고 표현하지만, 알고리즘 점화식의 귀납법에서는 'n + 1'이라는 표현을 쓰지 않는다. 항상 "n보다 작은 값에서 성립한다고 가정하고, n에서 성립함을 보인다"는 형태를 취한다.

귀납법 예제

연습 문제

1. 행렬 곱셈 -- 반복적(Iterative) 풀이의 시간 복잡도

다음 반복적 행렬 곱셈 알고리즘의 시간 복잡도를 구하라.

3중 for 루프가 존재하므로, 시간 복잡도는 $\Theta(n^3)$이다.

2. 행렬 곱셈 -- 분할 정복(Recursive) 풀이

Q1. 분할 정복 알고리즘의 시간 복잡도 $T(n)$을 점화식으로 표현하라.

Q2. 재귀 트리 방법으로 풀기

Q3. 마스터 정리로 풀기

수업 중 연습 문제

1. 재귀 트리

최종 결과: $\Theta(n \lg^2 n)$

2. 같은 문제를 마스터 정리로

이 문제는 마스터 정리의 세 가지 케이스 어디에도 정확히 해당하지 않는다. 즉, 마스터 정리로 커버되지 않는 경우가 존재하며, 이럴 때는 재귀 트리와 같은 다른 방법을 사용해야 한다.

3. 마스터 정리 적용

4. 수학적 귀납법으로 증명

증명: $1 + 3 + 5 + \cdots + (2n-1) = n^2$

Base case: $n = 1$일 때, $1^2 = 1$이므로 성립한다.

Inductive hypothesis: $n > 0$에 대해, $k \geq 0$이고 k < n인 모든 $k$에서 $1 + 3 + 5 + \cdots + (2k - 1) = k^2$이 성립한다고 가정한다. 이 가정에 의해 $k = n - 1$일 때 공식이 참이므로:

$1 + 3 + 5 + \cdots + (2n - 3) = (n - 1)^2$

Proof of goal statement:

$1 + 3 + 5 + \cdots + (2n-3) + (2n-1) = (n-1)^2 + (2n-1) = n^2$

따라서 $n$일 때도 성립한다. $\blacksquare$

5. 재귀 트리

6. Fibonacci 알고리즘의 시간 복잡도

1) 시간 복잡도 $T(n)$을 점화식으로 표현하라.

분할(Divide)과 결합(Combine) 모두 $\Theta(1)$이므로:

2) 이 알고리즘의 수행 시간(하한/상한)은?

7. 마스터 정리의 세 케이스에 해당하지 않을 때

마스터 정리의 케이스 1, 2, 3 어디에도 해당하지 않는 경우가 있다. 이때 다음과 같은 확장된 형태를 적용할 수 있다.

$f(n) = \Theta(n^{\log_b a} \lg^k n)$이고 $k \geq 0$이면:

$T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$

이 규칙은 $f(n)$이 $n^{\log_b a}$와 다항적 차이가 아닌 로그 인수(Logarithmic Factor) 만큼만 차이가 나는 경우에 해당한다.

HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.