재귀와 동적 계획법: 큰 문제를 작게 나누기

자기보다 작은 같은 문제에 일을 맡기는 재귀를 호출 과정을 찍어 보며 이해하고, 재귀 깊이 한계와 반복문으로 바꾸는 법을 익혀요. 반씩 나눠 곱셈 100만 번을 27번으로 줄이는 빠른 거듭제곱, 호출이 269만 번으로 불어나는 피보나치를 31번으로 줄이는 기억해 두기(메모이제이션)와 표 채우기를 비교해요. 큰 동전부터 고르는 탐욕법이 틀리는 거스름돈 문제와 오타를 교정하는 편집 거리로 동적 계획법을 설계하는 순서를 연습해요.

고급강의 6 / 6약 14분

지난 강의에서 폴더 크기를 구할 때 "폴더의 크기는 안에 든 것들의 크기의 합"이라고 정하고, 같은 함수를 안쪽 폴더에 다시 불렀어요. 이렇게 함수가 자기 자신을 부르는 게 재귀예요. 알고리즘 트랙의 마지막 강의에서는 재귀를 제대로 이해하고, 재귀가 같은 계산을 쓸데없이 되풀이할 때 그걸 없애는 동적 계획법까지 다뤄요.

재귀의 두 가지 재료

재귀 함수에는 두 가지가 꼭 있어야 해요.

  • 기저 사례: 더 쪼갤 필요 없이 바로 답할 수 있는 가장 작은 문제예요.
  • 재귀 단계: 지금 문제를 나보다 작은 같은 문제로 바꿔 나 자신에게 맡기고, 돌아온 답으로 내 답을 만들어요.

중첩된 리스트의 합을 구하면서 호출이 어떻게 쌓이고 풀리는지 찍어 볼게요.

def nested_sum(items, depth=0):
    pad = "    " * depth
    print(f"{pad}{items} 계산 시작")
    total = 0
    for x in items:
        if isinstance(x, list):
            total += nested_sum(x, depth + 1)        # 나보다 작은 같은 문제를 맡겨요
        else:
            total += x                               # 더 쪼갤 필요 없는 기저 사례
    print(f"{pad}{items} = {total}")
    return total

nested_sum([1, [2, 3], [4, [5, 6]]])
[1, [2, 3], [4, [5, 6]]] 계산 시작
    [2, 3] 계산 시작
    [2, 3] = 5
    [4, [5, 6]] 계산 시작
        [5, 6] 계산 시작
        [5, 6] = 11
    [4, [5, 6]] = 15
[1, [2, 3], [4, [5, 6]]] = 21

들여쓰기가 깊어질수록 호출이 쌓인 거예요. 맨 바깥 호출은 [4, [5, 6]]의 답을 기다리고, 그 호출은 다시 [5, 6]의 답을 기다려요. 가장 안쪽이 숫자만 더해 답을 돌려주면, 기다리던 호출들이 차례로 풀리며 바깥으로 올라와요. 리스트가 얼마나 깊이 중첩돼 있는지 몰라도 코드는 그대로예요. 폴더, JSON, HTML처럼 중첩된 구조를 다룰 때 재귀가 자연스러운 이유예요.

재귀를 짤 때는 호출을 머릿속으로 끝까지 따라가려 하지 말고, "작은 문제는 이 함수가 알아서 풀어 준다고 믿고, 그 답으로 내 문제를 어떻게 풀까"만 생각하는 게 요령이에요. 증명 강의의 수학적 귀납법과 같은 구조예요. 기저 사례의 답이 맞고, 작은 문제의 답이 맞을 때 큰 문제의 답도 맞게 만들면 모든 크기에서 맞아요.

호출 스택과 깊이 한계

함수를 부를 때마다 "끝나면 돌아올 곳"과 지역 변수가 호출 스택에 쌓여요(선형 구조 강의). 재귀가 깊어지면 스택도 그만큼 높아지는데, 파이썬은 너무 깊어지지 않게 한계를 둬요.

import sys

def count_down(n):
    return 0 if n == 0 else count_down(n - 1)

print("재귀 깊이 한계:", sys.getrecursionlimit())
print("900단계:", count_down(900))
try:
    count_down(5_000)
except RecursionError as e:
    print("5,000단계:", type(e).__name__)

def count_down_loop(n):                              # 같은 일을 반복문으로
    while n > 0:
        n -= 1
    return 0

print("반복문으로 100만 단계:", count_down_loop(1_000_000))
재귀 깊이 한계: 1000
900단계: 0
5,000단계: RecursionError
반복문으로 100만 단계: 0

900단계는 괜찮지만 5,000단계는 RecursionError가 나요. sys.setrecursionlimit로 한계를 올릴 수는 있지만, 너무 올리면 프로그램이 통째로 죽을 수 있어요. 깊이가 데이터 크기에 비례하는 재귀(연결 리스트 따라가기, 한 줄로 길게 이어진 그래프)는 반복문이나 직접 만든 스택으로 바꾸는 게 안전해요. 지난 강의의 height와 in_order가 그렇게 짠 예예요. 반대로 반씩 나누는 재귀는 깊이가 log n이라 걱정할 필요가 없어요. 100만 개를 나눠도 20단계쯤이거든요.

분할 정복: 반으로 나눠 풀기

문제를 비슷한 크기의 작은 문제 몇 개로 나눠 각각 풀고 합치는 방식을 분할 정복이라고 해요. 정렬 강의의 병합 정렬이 대표적이에요. 거듭제곱도 이렇게 빨라져요. 3의 1,000제곱은 3의 500제곱을 제곱한 것이고, 3의 500제곱은 3의 250제곱을 제곱한 것이에요.

def slow_power(x, n, mod):                           # x를 n번 곱해요
    result, mults = 1, 0
    for _ in range(n):
        result = result * x % mod
        mults += 1
    return result, mults

def fast_power(x, n, mod):                           # 반으로 나눠 구한 답을 제곱해요
    if n == 0:
        return 1, 0
    half, mults = fast_power(x, n // 2, mod)
    result = half * half % mod
    mults += 1
    if n % 2:                                        # n이 홀수면 x를 한 번 더 곱해요
        result = result * x % mod
        mults += 1
    return result, mults

MOD = 1_000_000_007
for n in (10, 1_000, 1_000_000):
    a, slow = slow_power(3, n, MOD)
    b, fast = fast_power(3, n, MOD)
    print(f"3의 {n:,}제곱: 답이 같나요? {a == b} | 곱셈 {slow:,}번 대 {fast}번")
print("3의 10¹⁸제곱도 순식간에:", pow(3, 10**18, MOD))
3의 10제곱: 답이 같나요? True | 곱셈 10번 대 6번
3의 1,000제곱: 답이 같나요? True | 곱셈 1,000번 대 16번
3의 1,000,000제곱: 답이 같나요? True | 곱셈 1,000,000번 대 27번
3의 10¹⁸제곱도 순식간에: 246336683

100만 번 곱하던 걸 27번으로 끝냈어요. n이 두 배가 돼도 곱셈은 한두 번 늘 뿐이라 O(log n)이에요. 수가 너무 커지지 않게 매번 나머지를 구했는데(% mod), RSA 같은 공개키 암호는 수백 자리 수의 거듭제곱을 바로 이 방법으로 계산해요. 파이썬의 pow(x, n, mod)도 이 방법을 써서, 지수가 10¹⁸이어도 순식간에 끝나요.

같은 계산을 되풀이하는 재귀

재귀가 늘 효율적인 건 아니에요. 앞의 두 수를 더해 다음 수를 만드는 피보나치 수를 정의 그대로 재귀로 짜면 어떻게 될까요?

from functools import cache

calls = 0
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

for n in (10, 20, 30):
    calls = 0
    value = fib(n)
    print(f"fib({n}) = {value:,} | 함수 호출 {calls:,}번")

memo_calls = 0
@cache                                               # 한 번 계산한 답은 기억해 둬요
def fib_memo(n):
    global memo_calls
    memo_calls += 1
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

print(f"기억해 두면: fib_memo(30) = {fib_memo(30):,} | 함수 호출 {memo_calls}번")

def fib_table(n):                                    # 작은 것부터 표를 채워 올라가기
    table = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(f"표로 채우면: fib_table(30) = {fib_table(30):,} | fib_table(300)은 {len(str(fib_table(300)))}자리 수")
fib(10) = 55 | 함수 호출 177번
fib(20) = 6,765 | 함수 호출 21,891번
fib(30) = 832,040 | 함수 호출 2,692,537번
기억해 두면: fib_memo(30) = 832,040 | 함수 호출 31번
표로 채우면: fib_table(30) = 832,040 | fib_table(300)은 63자리 수

fib(30)을 구하려고 함수를 269만 번 불렀어요. n이 10 늘 때마다 호출이 100배 넘게 늘어나는 지수 시간이에요. 이유는 같은 계산을 계속 다시 하기 때문이에요. fib(30)은 fib(29)와 fib(28)을 부르는데, fib(29)도 fib(28)을 또 불러요. 아래로 갈수록 같은 호출이 눈덩이처럼 불어나요. 이렇게 작은 문제가 여러 번 겹쳐 나오는 걸 겹치는 부분 문제라고 해요.

해결은 간단해요. 한 번 계산한 답을 기억해 두는 거예요. @cache를 붙이면 같은 인자로 다시 불렀을 때 계산하지 않고 기억해 둔 답을 돌려줘요. 이걸 메모이제이션이라고 해요. fib(0)부터 fib(30)까지 한 번씩, 31번이면 끝나요. 해시 테이블 강의에서 말한 "계산 결과 기억해 두기"가 바로 이거예요.

아예 재귀를 쓰지 않고 작은 것부터 표를 채워 올라갈 수도 있어요. fib_table은 fib(2), fib(3)의 순서로 채우니 재귀 깊이 걱정도 없어요. 이렇게 겹치는 부분 문제의 답을 저장해 두고 큰 문제를 푸는 방법을 동적 계획법이라고 해요. 위에서 내려오며 기억해 두는 방식과 아래에서 표를 채워 올라가는 방식 모두 동적 계획법이에요. 이름의 "계획(programming)"은 코드를 짠다는 뜻이 아니라 표를 짜서 계획한다는 옛 뜻이에요.

동적 계획법 설계하기: 거스름돈

동적 계획법 문제는 대개 이 순서로 설계해요.

  1. 상태 정하기: "best[a]는 a원을 만드는 가장 적은 동전 묶음"처럼, 표의 한 칸이 무엇을 뜻하는지 정해요.
  2. 점화식 세우기: 그 칸을 더 작은 칸들로 나타내요. a원을 만드는 마지막 동전이 c라면, 나머지는 (a - c)원의 최선이에요. 동전마다 따져 보고 가장 적은 걸 골라요.
  3. 기저 사례 정하기: 0원은 동전 0개예요.
  4. 채우는 순서 정하기: 작은 칸이 먼저 채워져 있어야 하니 0원부터 올라가요.

큰 동전부터 최대한 쓰는 탐욕법과 비교해 볼게요.

def greedy_coins(coins, amount):                     # 큰 동전부터 최대한 많이
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None

def dp_coins(coins, amount):                         # best[a] = a원을 만드는 가장 적은 동전 묶음
    best = [[]] + [None] * amount
    for a in range(1, amount + 1):                   # 작은 금액부터 차례로 채워요
        for c in coins:
            if c <= a and best[a - c] is not None:
                candidate = best[a - c] + [c]        # (a - c)원의 최선에 동전 c를 하나 더하면
                if best[a] is None or len(candidate) < len(best[a]):
                    best[a] = candidate
    return best[amount]

for coins, amount in [([10, 50, 100, 500], 780), ([1, 7, 10], 14)]:
    g, d = greedy_coins(coins, amount), sorted(dp_coins(coins, amount), reverse=True)
    print(f"동전 {coins}, {amount}원 만들기")
    print(f"    큰 것부터: {len(g)}개 {g}")
    print(f"    동적 계획법: {len(d)}개 {d}")
동전 [10, 50, 100, 500], 780원 만들기
    큰 것부터: 7개 [500, 100, 100, 50, 10, 10, 10]
    동적 계획법: 7개 [500, 100, 100, 50, 10, 10, 10]
동전 [1, 7, 10], 14원 만들기
    큰 것부터: 5개 [10, 1, 1, 1, 1]
    동적 계획법: 2개 [7, 7]

한국 동전으로는 큰 것부터 고르는 방법도 최선이에요. 하지만 동전이 1원, 7원, 10원이라면 14원을 10 + 1 + 1 + 1 + 1의 5개로 만들어 버려요. 7 + 7, 2개가 최선인데요. 탐욕법은 지금 당장 가장 좋아 보이는 것을 고르고 되돌아보지 않아서, 처음 고른 10원이 나중에 손해가 돼도 모르는 거예요. 동적 계획법은 모든 금액에 대해 "마지막 동전이 무엇이었을까"를 빠짐없이 따지니 언제나 최선을 찾아요. 시간은 금액과 동전 종류 수의 곱이에요.

탐욕법이 늘 틀리는 건 아니에요. 한국 동전처럼 탐욕법이 최선이라는 게 증명된 경우도 있고, 그럴 때는 훨씬 빠르고 간단해요. 회의실 하나에 회의를 최대한 많이 넣으려면 "끝나는 시간이 가장 이른 회의부터" 고르면 되는 것도 그런 예예요. 지난 강의의 다익스트라도 "지금 가장 가까운 곳부터"를 고르는 탐욕법이에요. 다만 증명 없이 탐욕법을 믿으면 위처럼 조용히 틀린 답을 내요.

편집 거리: 오타 교정

검색창에 "알고리즌"이라고 쳐도 "알고리즘"을 찾아 주는 기능을 만들어 볼게요. 두 단어가 얼마나 다른지는 편집 거리로 재요. 한 글자를 지우거나, 넣거나, 바꾸는 것을 한 번으로 쳐서, 한 단어를 다른 단어로 바꾸는 데 필요한 최소 횟수예요.

상태는 "a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 횟수"예요. 마지막 글자를 어떻게 처리했는지는 셋 중 하나예요. a의 마지막 글자를 지웠거나, b의 마지막 글자를 넣었거나, 바꿨거나(같은 글자면 그대로 두니 0번)요. 셋 중 가장 작은 걸 고르면 돼요.

def edit_distance(a, b):
    prev = list(range(len(b) + 1))                   # 빈 문자열에서 b의 앞부분을 만드는 비용
    for i, ca in enumerate(a, 1):
        cur = [i]                                    # a의 앞 i글자를 빈 문자열로: i번 지우기
        for j, cb in enumerate(b, 1):
            cur.append(min(prev[j] + 1,              # a의 글자를 지우거나
                           cur[j - 1] + 1,           # b의 글자를 넣거나
                           prev[j - 1] + (ca != cb)))   # 바꾸거나(같은 글자면 0)
        prev = cur
    return prev[-1]

print("kitten → sitting:", edit_distance("kitten", "sitting"))
print("알고리즘 → 알고리듬:", edit_distance("알고리즘", "알고리듬"))

words = ["알고리즘", "자료구조", "데이터베이스", "네트워크", "운영체제", "컴파일러"]
for typo in ["알고리즌", "데이타베이스", "네트웍"]:
    guess = min(words, key=lambda w: edit_distance(typo, w))
    print(f"'{typo}'? 혹시 '{guess}' 말인가요? (거리 {edit_distance(typo, guess)})")
kitten → sitting: 3
알고리즘 → 알고리듬: 1
'알고리즌'? 혹시 '알고리즘' 말인가요? (거리 1)
'데이타베이스'? 혹시 '데이터베이스' 말인가요? (거리 1)
'네트웍'? 혹시 '네트워크' 말인가요? (거리 2)

표 전체는 (a의 길이 + 1) × (b의 길이 + 1)칸이지만, 한 줄을 채울 때 바로 윗줄만 필요해서 두 줄만 들고 다녔어요. 동적 계획법에서 자주 쓰는 메모리 절약법이에요. 시간은 두 길이의 곱이에요. 맞춤법 검사, 검색어 교정, DNA 서열 비교가 이런 방식으로 돌아가고, git diff가 두 파일에서 바뀐 줄을 찾는 것도 같은 집안의 알고리즘이에요.

네 가지 방법 정리

방법언제 쓰나예
재귀문제가 같은 모양의 작은 문제로 나뉠 때중첩 구조 처리, 트리 순회
분할 정복나눈 작은 문제들이 서로 겹치지 않을 때병합 정렬, 빠른 거듭제곱, 이진 탐색
동적 계획법작은 문제들이 여러 번 겹쳐 나올 때피보나치, 거스름돈, 편집 거리
탐욕법지금의 최선이 전체의 최선이라고 증명될 때한국 동전 거스름돈, 회의실 배정, 다익스트라

동적 계획법으로도 감당하지 못하는 문제도 있어요. 조합론 강의에서 본 외판원 문제처럼, 작은 문제로 나눠도 그 수가 지수적으로 많은 경우예요. 이런 문제가 왜 어려운지는 컴퓨터 과학 이론 트랙의 계산 복잡도 강의에서 다뤄요.

실습

  1. nested_sum을 재귀 없이, 직접 만든 스택으로 바꿔 보세요.
  2. fast_power를 반복문으로 바꿔 보세요. 힌트: n을 이진수로 보고, 자리마다 x를 제곱해 가며 1인 자리에서만 결과에 곱해요.
  3. 계단을 한 번에 1칸이나 2칸씩 오를 때, 10칸을 오르는 방법은 몇 가지일까요? 상태와 점화식을 먼저 세우고 표를 채워 보세요.
  4. 가방에 7kg까지 넣을 수 있고 물건이 (무게, 가치)로 (1kg, 1,000원), (3kg, 4,000원), (4kg, 5,000원), (5kg, 7,000원)일 때, 가치의 합이 가장 큰 조합을 동적 계획법으로 찾아보세요. 0/1 배낭 문제라고 불러요.
  5. dp_coins는 칸마다 동전 묶음 전체를 저장해요. 칸마다 "동전 개수"와 "마지막에 쓴 동전"만 저장하고, 마지막에 거꾸로 따라가 묶음을 복원하도록 고쳐 보세요.

자주 하는 실수

  • 기저 사례를 빠뜨린다. 끝없이 자기를 불러 RecursionError가 나요.
  • 문제를 작게 만들지 않고 부른다. 같은 크기로 다시 부르면 역시 끝나지 않아요. 부를 때마다 반드시 기저 사례에 가까워져야 해요.
  • 겹치는 부분 문제를 매번 다시 푼다. 정의 그대로 짠 재귀가 지수 시간이 되는 흔한 원인이에요. 기억해 두거나 표를 채워요.
  • @cache를 아무 데나 붙인다. 인자가 리스트처럼 해시할 수 없으면 오류가 나고(해시 테이블 강의), 인자 종류가 끝없이 많으면 기억이 쌓여 메모리를 채워요. 그럴 땐 lru_cache(maxsize=...)로 크기를 정해요.
  • 탐욕법을 증명 없이 믿는다. 1원, 7원, 10원 동전처럼 조용히 틀린 답을 내요.
  • 깊이가 데이터 크기만큼인 재귀를 쓴다. 재귀 깊이 한계에 걸려요. 반복문으로 바꿔요.

점검 문제

  1. 재귀 함수에 꼭 있어야 하는 두 가지는?
  2. 재귀를 짤 때 "작은 문제는 이미 풀린다고 믿는" 방식이 맞는 이유는?
  3. 파이썬에서 깊은 재귀가 위험한 이유와 대처법은?
  4. 빠른 거듭제곱이 곱셈을 O(log n)번만 하는 이유는?
  5. 정의 그대로 짠 피보나치 재귀가 느린 이유와, 고치는 두 가지 방법은?
  6. 동적 계획법을 설계하는 순서를 말해 보세요.
  7. 큰 동전부터 고르는 방법이 1원, 7원, 10원 동전으로 14원을 만들 때 틀리는 이유는?
  8. 편집 거리의 상태는 무엇이고, 한 칸을 채울 때 따지는 세 가지 경우는?

정답

  1. 바로 답할 수 있는 가장 작은 문제(기저 사례)와, 지금 문제를 나보다 작은 같은 문제로 바꿔 맡기는 재귀 단계예요.
  2. 수학적 귀납법과 같은 구조라서요. 기저 사례의 답이 맞고, 작은 문제의 답이 맞을 때 큰 문제의 답도 맞게 만들면 모든 크기에서 답이 맞아요.
  3. 호출마다 호출 스택이 쌓이는데 파이썬은 깊이 한계(기본 1,000)가 있어서 RecursionError가 나요. 깊이가 데이터 크기에 비례하면 반복문이나 직접 만든 스택으로 바꿔요.
  4. 지수를 매번 반으로 줄여 가며 구한 답을 제곱하니, 단계가 log₂ n개이고 단계마다 곱셈은 한두 번뿐이기 때문이에요.
  5. 같은 작은 문제를 계속 다시 계산해서 호출이 지수적으로 불어나기 때문이에요. 한 번 계산한 답을 기억해 두거나(메모이제이션), 작은 것부터 표를 채워 올라가면 n번 정도로 끝나요.
  6. 표의 한 칸이 무엇을 뜻하는지(상태) 정하고, 그 칸을 더 작은 칸들로 나타내는 점화식을 세우고, 기저 사례를 정하고, 작은 칸이 먼저 채워지도록 채우는 순서를 정해요.
  7. 처음에 가장 큰 10원을 고르면 남은 4원을 1원 4개로 채울 수밖에 없는데, 탐욕법은 한 번 고른 것을 되돌아보지 않기 때문이에요. 7원 2개가 최선이에요.
  8. 상태는 "a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 횟수"예요. a의 마지막 글자를 지우는 경우, b의 마지막 글자를 넣는 경우, 마지막 글자를 바꾸는 경우(같은 글자면 0번)를 따져 가장 작은 값을 골라요.

다음 강의

알고리즘 트랙을 마쳤어요. 복잡도를 읽는 눈부터 배열과 해시 테이블, 정렬, 트리와 그래프, 재귀와 동적 계획법까지, 같은 결과를 더 빠르고 적은 자원으로 얻는 도구를 갖췄어요. 다음은 컴퓨터 과학 이론 트랙이에요. 지금까지는 컴퓨터가 계산을 해 준다고 믿고 썼는데, 그 계산이 전기 신호로 어떻게 이뤄지는지 트랜지스터와 논리 게이트에서 시작해 덧셈기까지 직접 쌓아 올려 봐요.