점화식: 앞 답으로 다음 답 만들기

계단 30칸을 한 번에 1칸 또는 2칸씩 올라간다. 오르는 방법은 몇 가지일까? 답은 1,346,269가지다. 이 수를 "n칸을 오르는 방법 = 마지막 걸음이 1칸인 방법 + 2칸인 방법"이라는 생각 그대로 재귀 함수로 짜면 세 줄이면 된다. 그런데 답 하나를 구하는 동안 함수가 1,664,079번 불린다. 같은 생각을 표에 차례로 채우는 반복문으로 짜면 30번 안팎으로 끝난다. 같은 식인데 왜 이렇게 다를까?

"n칸의 답 = (n − 1)칸의 답 + (n − 2)칸의 답"처럼 앞 답으로 다음 답을 정하는 식을 점화식(recurrence relation)이라고 한다. 이 Unit은 점화식을 세우는 법, 표로 채우는 법, 그대로 재귀로 옮겼을 때 호출 수가 어떻게 되는지, 그리고 반으로 나눠 풀고 합치는 일의 양이 점화식으로 어떻게 n log n이 되는지를 차례로 본다.

계단 오르기: 마지막 걸음으로 나눈다

계단을 한 번에 1칸 또는 2칸씩 오른다. 4칸을 오르는 방법은 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지다. 10칸이면 손으로 적기 어렵다. 그래서 하나하나 적는 대신 마지막 걸음으로 나눠 센다.

n칸 꼭대기에 닿기 직전의 마지막 걸음은 1칸이거나 2칸이다.

• 마지막 걸음이 1칸이면, 그 전에 n − 1칸까지 올라와 있었다. 그 방법의 수가 f(n − 1)이다.
• 마지막 걸음이 2칸이면, 그 전에 n − 2칸까지 올라와 있었다. 그 방법의 수가 f(n − 2)다.

두 무리는 겹치지 않는다(마지막 걸음이 다르다). 그리고 모든 방법은 둘 중 하나에 들어간다. Unit 6에서 "둘 중 하나면 더한다"고 했으니 두 수를 더한다.

$f(n) = f(n-1) + f(n-2)$

"n칸을 오르는 방법의 수는 n − 1칸의 답과 n − 2칸의 답을 더한 것"이라고 읽는다. 4칸이면 f(4) = f(3) + f(2) = 3 + 2 = 5로, 손으로 센 5가지와 같다.

이 식만으로는 계산을 시작할 수 없다. f(3)을 구하려면 f(2)와 f(1)이, f(2)를 구하려면 f(1)과 f(0)이 필요해 끝없이 내려간다. 그래서 식을 쓰지 않고 바로 아는 맨 처음 답, 곧 시작 값(base case)을 정해 둔다. 1칸은 한 가지(1), 2칸은 두 가지(1+1, 2)다. 『한입 알고리즘』 5장이 재귀가 멈추는 "바닥"이라고 부른 것이 이 시작 값이다.

1const n = 62const ways = new Array(n + 1).fill(0)3ways[1] = 14ways[2] = 25for (let i = 3; i <= n; i++) {6  ways[i] = ways[i - 1] + ways[i - 2]7  console.log(`${i}칸: ${ways[i]}가지`)8}

3칸: 3가지
4칸: 5가지
5칸: 8가지
6칸: 13가지

이 수열은 피보나치 수(0, 1, 1, 2, 3, 5, 8, …)라는 유명한 수열과 같은 점화식이다(『한입 알고리즘』 10장은 이 수열로 동적 계획법을 시작한다). 시작 값만 달라서 한 칸 밀려 있다. f(n)은 fib(n + 1)이다. 표를 채우는 코드는 칸마다 덧셈 한 번이라 칸 수만큼, n번 남짓 일한다.

그대로 재귀로 쓰면: 호출이 불어난다

점화식은 생긴 모양이 이미 재귀(recursion) 함수다. f(n)이 f(n − 1)과 f(n − 2)를 부르고, 시작 값에서 멈춘다. 그대로 옮기면 세 줄이다. 재귀의 개념 정리는 재귀 노트에 있다.

1const n = 52const order: number[] = []3function climb(k: number): number {4  order.push(k)5  if (k <= 2) return k6  return climb(k - 1) + climb(k - 2)7}8const answer = climb(n)9console.log(`climb(${n}) = ${answer}, 호출 ${order.length}번`)

climb(5) = 8, 호출 9번

호출 수를 c(n)이라 하면, climb(n) 한 번이 climb(n − 1)과 climb(n − 2)를 부르니 호출 수에도 비슷한 점화식이 선다.

$c(n) = 1 + c(n-1) + c(n-2)$

"climb(n)의 호출 수는 자기 자신 1번에, 두 갈래의 호출 수를 더한 것"이라고 읽는다. 시작 값 c(1) = c(2) = 1에서 c(3) = 1 + 1 + 1 = 3, c(4) = 1 + 3 + 1 = 5, c(5) = 1 + 5 + 3 = 9다.

메모 없는 쪽은 n이 1 늘 때마다 약 1.6배가 된다. 점화식으로 이어 구한 c(5) = 9, c(6) = 15, c(7) = 25, c(8) = 41, c(9) = 67, c(10) = 109에서 이웃한 n끼리 나누면 15/9 ≈ 1.67, 41/25 ≈ 1.64, 109/67 ≈ 1.63으로 1.6 쪽으로 다가간다. 표의 이웃 칸으로 확인하면 13,529(20칸) → 1,664,079(30칸)는 10칸에 약 123배이고, 1.6을 열 번 곱하면 약 110이다(정확한 배율은 1.618…이라 열 번 곱하면 123). 호출 하나가 둘을 부르고 그 둘이 또 둘씩 부르니, 갈래가 2배씩 늘어나는 Unit 6의 부분집합 탐색과 닮았다. 한 갈래(n − 2)가 조금 짧아서 정확히 2배가 아니라 1.6배일 뿐, 곱으로 불어나는 지수 모양은 같다. 40칸이면 2억 번이 넘는다.

고칠 곳은 하나다. climb(k)의 답을 한 번 구하면 memo에 적어 두고, 다시 불리면 계산하지 않고 꺼낸다. 이렇게 한 번 계산한 답을 적어 두는 기법을 메모이제이션(memoization)이라고 한다. 그러면 k마다 직접 푸는 것은 한 번뿐이고, 호출 수는 2n − 3번이 된다. 6칸이면 2 × 6 − 3 = 9로 표와 같다. 3칸부터 n칸까지 직접 푸는 호출 n − 2번에, 메모나 시작 값에서 바로 돌아오는 호출 n − 1번을 더한 수다. 40칸도 77번이다. 일이 n에 비례하니 Big-O로 O(n)이다(Big-O는 빅오 표기법 노트). 이렇게 작은 문제의 답을 적어 두고 큰 문제의 답을 조립하는 방법이 동적 계획법(dynamic programming)이다(동적 계획법 노트). 앞 절의 표 채우기도 같은 방법을 작은 칸부터 채우는 순서로 한 것이다.

분할 정복: T(n) = 2T(n/2) + n을 층으로 그리기

점화식은 답의 개수만이 아니라 일의 양도 적는다. 병합 정렬(merge sort)은 배열을 반으로 나눠 각각 정렬한 뒤, 정렬된 두 반쪽을 합친다. 합칠 때는 두 반쪽의 맨 앞을 비교해 작은 것을 하나씩 꺼내므로, 원소 n개를 합치는 데 n만큼 일한다. 이렇게 같은 모양의 작은 문제로 나눠 풀고 답을 합치는 방법을 분할 정복(divide and conquer)이라고 한다(병합 정렬, 분할 정복 노트).

크기 n을 정렬하는 일을 T(n)이라 하면(T는 time의 T, 크기 n에 드는 일) 이렇게 적는다.

$T(n) = 2\,T\!\left(\frac{n}{2}\right) + n$

"크기 n을 처리하는 일은, 크기 n/2를 처리하는 일 두 번에 합치는 일 n을 더한 것"이라고 읽는다. 시작 값은 T(1) = 0이다. 원소 하나는 이미 정렬돼 있다. 이 식을 손으로 풀어 내려가면 헷갈리니, 일을 층으로 그려 본다.

층마다 n인 이유는 이렇다. 한 층 내려갈 때마다 조각 수는 두 배가 되고 조각 크기는 절반이 된다. 조각 수 × 조각 크기는 그대로 n이다.

층 수는 n을 1이 될 때까지 반으로 접는 횟수, Unit 2의 로그(logarithm) log₂n이다. 8은 세 번(8 → 4 → 2 → 1), 1,024는 열 번 접는다. 전체 일은 층마다 n을 log₂n번 더한 합이고, 같은 수 n을 log₂n번 더하면 n × log₂n이다.

$n \times \log_2 n = 8 \times 3 = 24$

"층마다 n씩, log₂n층"이라고 읽는다. 그래서 병합 정렬은 O(n log n)이다. n = 1,024면 1,024 × 10 = 10,240이고, 모든 쌍을 비교하는 n² = 1,048,576보다 100배쯤 적다. 점화식을 외운 공식으로 풀 필요는 없다. 층을 그리고 "층마다 일이 얼마인가", "층이 몇 개인가"를 물으면 된다.

실무 코드에서 찾아보기

검토 기준은 앞 절에 다 나왔다. 바닥이 되는 답을 빠짐없이 정했는가(1절), 칸 수가 늘 때 결과가 number에 다 담기는가(Unit 6 5절), 이미 구한 칸을 또 계산하지 않는가(2절)를 줄마다 견준다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 10장 동적 계획법: fib(n) = fib(n − 1) + fib(n − 2)가 이 Unit의 계단 점화식과 같은 모양이다. 정의를 그대로 옮긴 재귀가 fib(5)에서 15번 불리고 메모이제이션으로 2n − 1번이 되는 것이 2절의 호출 수 표와 같은 현상이다(이 Unit의 계단은 시작 값이 두 개라 2n − 3번). LCS 표의 dp[i][j]를 이웃 칸으로 채우는 규칙도 점화식이다.
• 『한입 알고리즘』 5장 DFS와 백트래킹: "폴더 용량 = 자기 폴더에 바로 든 파일 용량 + 하위 폴더 용량의 합"이 점화식이고, "재귀가 멈추는 바닥(base case)"이 시작 값이다.
• 『한입 알고리즘』 7장 정렬: 보너스 문제의 병합 정렬에서 단계마다 병합이 원소 전체를 한 번씩 보고(O(n)), 조각 길이가 두 배씩 자라 단계가 log n번이라는 설명이 3절의 층 그림이다.
• 『한입 알고리즘』 6장 이분 탐색: 한 번 비교할 때마다 후보가 절반이 되어 100만 개도 20번이면 끝나는 것이 T(n) = T(n/2) + 1, 층마다 1씩 log₂n층이다.

(가) n = 8 → 층별 일 ?, 합 ?
(나) n = 8 → 층별 일 ?, 합 ?
(다) n = 8 → 층별 일 ?, 합 ?