22.1 하노이의 탑 The Towers of Hanoi

점화식 이야기를 시작할 때 거의 모든 교재가 꺼내드는 단골손님이 있습니다. 바로 하노이의 탑입니다. 세 개의 막대 \( A, B, C \)가 있고, 막대 \( A \)에 크기가 서로 다른 원반 \( n \)개가 큰 것이 아래, 작은 것이 위로 쌓여 있어요. 우리는 이 원반들을 모두 막대 \( C \)로 옮겨야 합니다. 단, 규칙이 있습니다.

• 한 번에 원반은 하나만 움직일 수 있다.
• 큰 원반을 작은 원반 위에 올릴 수 없다.

이 문제의 매력은, 답을 머리로 풀려고 하면 금방 막히는데 재귀로 풀면 거짓말처럼 풀린다는 점입니다. 한번 같이 따라가 봐요.

핵심 아이디어는 이렇습니다. \( n \)개를 \( A \to C \)로 옮기고 싶으면, 먼저 위쪽 \( n-1 \)개를 \( A \to B \)로 옮긴 다음, 가장 큰 \( n \)번 원반을 \( A \to C \)로 옮기고, 마지막으로 \( B \)에 쌓아둔 \( n-1 \)개를 \( B \to C \)로 옮기면 됩니다. 큰 원반은 깔개 역할만 하므로 작은 원반들의 이동을 방해하지 않아요.

초기                  중간                  최종
 |       |       |     |       |       |     |       |       |
 _       |       |     |       |       |     |       |       _
__       |       |     |       _       |     |       |       __
___      |       |     |       __      |     |       |       ___
A        B       C     A       B       C     A       B       C
    

이 전략을 비용으로 바꿔 적으면 점화식이 됩니다. \( n \)개를 옮기는 데 필요한 최소 이동 횟수를 \( T(n) \)이라 하면, 위 절차에서 우리는 \( n-1 \)개 옮기기를 두 번, 그리고 가장 큰 원반 한 번을 옮깁니다.

점화식이 있으면 작은 값부터 직접 계산해 볼 수 있어요. \( T(0)=0,\; T(1)=1,\; T(2)=3,\; T(3)=7,\; T(4)=15,\; T(5)=31 \). 패턴이 보이나요? 1씩 더하면 모두 2의 거듭제곱입니다. 그럼 한번 추측해 봅시다. \( T(n) = 2^n - 1 \).

여담으로, 전설에 따르면 64개 원반을 어떤 사원의 승려들이 옮기고 있다고 합니다. 1초에 한 번씩 옮긴다 해도 \( 2^{64}-1 \approx 1.8 \times 10^{19} \)초, 약 5849억년이 걸립니다. 우주의 나이보다 훨씬 길죠. 알고리즘 시간복잡도가 왜 중요한지 이보다 직관적인 예가 있을까요.

def hanoi(n, src, via, dst):
    if n == 0: return
    hanoi(n-1, src, dst, via)
    print(f"{src} -> {dst}")
    hanoi(n-1, via, src, dst)

22.2 합병 정렬 Merge Sort

이제 좀 더 실용적인 친구를 봅시다. 합병 정렬(merge sort)은 \( n \)개의 원소를 정렬할 때, 배열을 절반으로 나눠 각각 정렬한 뒤 두 정렬된 부분을 합쳐 하나로 만드는 알고리즘이에요. 이 "나눠서 풀고 합친다"는 패턴이 바로 분할정복(divide-and-conquer)입니다.

비용을 \( T(n) \)이라 하면, 길이 \( n \) 배열에서 합병 정렬은 다음 일을 합니다.

1. 길이 \( n/2 \)짜리를 두 번 정렬: 비용 \( 2T(n/2) \).
2. 두 정렬된 배열을 하나로 합치는 merge: 비용 \( \Theta(n) \) (양쪽 끝에서 작은 쪽을 한 번씩 뽑아내며 \( n \)개 다 채우면 끝).

이 점화식을 손으로 풀어 봅시다. 가장 단순한 방법은 펼쳐쓰기(unrolling)입니다. 한 단계씩 안쪽으로 들어가면서 식을 풀어 보면,

\[ T(n) = 2T(n/2) + n = 2\big(2T(n/4) + n/2\big) + n = 4T(n/4) + 2n. \]

한 번 더 펼치면 \( 8T(n/8) + 3n \). \( k \)번 펼치면 \( 2^k T(n/2^k) + k\,n \). 이제 \( n/2^k = 1 \)이 될 때까지, 즉 \( k = \log_2 n \)까지 가면,

\[ T(n) = 2^{\log_2 n}\, T(1) + (\log_2 n)\, n = n \cdot 0 + n \log_2 n = n \log_2 n. \]

같은 결과를 그림으로도 볼 수 있어요. 재귀 트리(recursion tree)를 그려 봅시다. 루트에서 비용 \( n \), 다음 층에 비용 \( n/2 \)인 노드 두 개(합 \( n \)), 그 다음에 \( n/4 \)인 노드 네 개(합 \( n \))… 층마다 합이 \( n \)인 게 핵심입니다. 트리의 높이는 \( \log_2 n \)이므로 전체 비용은 \( n \log_2 n \).

            n            ← n
          /   \
        n/2    n/2        ← n
       / \    / \
     n/4 n/4 n/4 n/4      ← n
      ...                 ← ...
      1 1 1 ... 1         ← n  (leaves: 총 n개)
    높이 log₂ n
    

22.3 선형 점화식 Linear Recurrences

하노이는 \( T(n) = 2T(n-1)+1 \), 합병 정렬은 \( T(n) = 2T(n/2) + n \). 둘 다 자기 자신을 다시 부르지만, 부르는 방식이 다릅니다. 이 절에서는 첫 번째 종류, 즉 입력 크기를 상수만큼 줄이는 점화식을 정리합니다. 일반적으로 모양은

\[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_d a_{n-d} + f(n) \]

이고, 계수 \( c_i \)가 상수일 때 이를 상수계수 선형 점화식이라고 합니다. \( f(n)=0 \)이면 동차(homogeneous), 아니면 비동차(inhomogeneous)입니다.

특성근을 \( r_1, \ldots, r_d \)라 하고 모두 다르다면, 일반해는 이들의 선형결합입니다.

\[ a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_d r_d^n. \]

계수 \( \alpha_i \)는 초기조건(\( a_0, a_1, \ldots \))을 대입해 연립방정식으로 정합니다. 만약 어떤 근 \( r \)이 중근이라면 \( r^n,\, n r^n,\, n^2 r^n,\ldots \) 식으로 \( n \)을 곱한 항들을 추가해 주면 됩니다.

비동차 항 \( f(n) \)이 있을 때는 두 단계로 나눕니다. 먼저 동차 부분의 일반해 \( a_n^{(h)} \)를 구하고, \( f(n) \)에 어울리는 특수해 \( a_n^{(p)} \)를 추측해서 대입해 본 뒤, 둘을 더한 \( a_n = a_n^{(h)} + a_n^{(p)} \)로 일반해를 만듭니다.

22.4 분할정복 점화식 Divide-and-Conquer Recurrences

합병 정렬 같은 알고리즘의 비용은 일반적으로 다음 모양을 합니다.

\[ T(n) = a\,T(n/b) + f(n), \]

여기서 \( a \ge 1 \)은 부분문제 개수, \( b > 1 \)은 크기 축소 비율, \( f(n) \)은 분할과 결합에 드는 비용이에요. 이런 점화식의 차수를 한 방에 알려주는 도구가 바로 마스터 정리(Master Theorem)입니다.

왜 이런 모양이 나오는지 직관은 재귀 트리에 있습니다. 트리의 높이는 \( \log_b n \), \( k \)번째 층에는 노드가 \( a^k \)개, 각 노드의 비용이 \( f(n/b^k) \)예요. 잎의 개수는 \( a^{\log_b n} = n^{\log_b a} \). 따라서 비용이 어디에 몰리는지가 차수를 결정합니다.

• 경우 1: 잎 쪽이 무겁다. 합병 비용이 작아 잎이 비용을 지배 → \( n^{\log_b a} \).
• 경우 2: 모든 층이 비슷하게 무겁다. 층마다 \( \Theta(n^{\log_b a}) \), 층이 \( \log n \)개 → \( n^{\log_b a} \log n \).
• 경우 3: 루트 쪽이 무겁다. 루트의 \( f(n) \)이 비용을 지배 → \( f(n) \).

22.5 점화식 감각 익히기 A Feel for Recurrences

점화식을 잘 다루는 사람은 정리 하나를 외우고 있는 사람이 아니라, 답의 모양을 빠르게 추측하고 검증하는 사람입니다. 이 절에서는 그 감각을 위한 세 가지 도구를 정리합니다.

(1) 펼쳐쓰기(unrolling). 점화식을 한두 단계 풀어쓰고 패턴을 찾는 방법이에요. 22.2절에서 \( T(n) = 2T(n/2)+n \)을 펼쳐 \( 2^k T(n/2^k) + kn \) 꼴을 얻은 게 전형적인 예입니다. 일반항을 추측한 뒤, 귀납법으로 검증하면 끝.

(2) 재귀 트리(recursion tree). 부분문제를 트리로 그리고, 층별 비용을 합산하는 방법. 분할정복 점화식의 직관은 거의 항상 트리에서 옵니다. 마스터 정리의 세 경우도 결국 "어느 층이 비용을 지배하는가?"의 트리적 표현이에요.

(3) 추측-검증(guess and verify). 답이 \( O(n \log n) \)일 거라고 추측한 뒤, 강한 귀납법으로 \( T(n) \le c\,n \log n \)을 직접 증명하는 방법. 이걸 치환법(substitution method)이라고도 부릅니다. 추측만 적당히 하면 거의 모든 점화식을 잡을 수 있어요.

마지막으로 점화식을 만났을 때 머릿속에 둘 만한 실전 팁입니다.

• 점화식을 보자마자 "크기를 어떻게 줄이는가"를 묻자. \( n-1 \)인지, \( n/b \)인지에 따라 도구가 달라진다.
• 크기가 상수만큼 줄면(예: \( T(n)=T(n-1)+\cdots \)) 선형 점화식 도구(특성방정식)를 시도.
• 크기가 비율로 줄면(예: \( T(n)=aT(n/b)+f(n) \)) 마스터 정리부터 본다.
• 마스터 정리가 안 되면 재귀 트리를 그려본다. 거의 항상 답이 보인다.
• 그래도 안 풀리면 답의 형태를 추측하고 치환법으로 검증한다.
• 작은 \( n \)에 대해 직접 계산해 보고 OEIS(온라인 정수수열 사전)에 검색해 보는 것도 의외로 빠른 길이다.