피보나치의 메모이제이션과 반복

피보나치 수열은 0과 1에서 시작해, 그다음 수부터는 바로 앞 두 수의 합으로 이어지는 수열입니다. 0, 1, 1, 2, 3, 5, 8, 13으로 이어지며, 식으로는 F(0) = 0, F(1) = 1이고 n이 2 이상이면 F(n) = F(n - 1) + F(n - 2)입니다. 정의가 이미 재귀의 모양이라서 코드로 옮기기는 쉽지만, 정의대로 계산하면 n이 조금만 커져도 끝나지 않습니다. 이 글에서는 그 이유를 호출 횟수로 확인하고, 앞 글에서 본 동적 계획법을 두 가지 방식으로 적용합니다. 하나는 재귀의 모양을 유지하면서 구한 답을 저장하는 방식이고, 다른 하나는 작은 수부터 차례로 표를 채우는 방식입니다.

정의대로 계산하면

정의를 그대로 옮긴 재귀 함수에, n마다 몇 번 불렸는지 세는 딕셔너리를 붙여 보겠습니다. 함수의 첫 줄 counter[n] = counter.get(n, 0) + 1이 인자 n으로 불릴 때마다 그 칸을 1씩 늘리므로, 실행이 끝나면 n별 호출 횟수가 남습니다. F(5)에서는 이 횟수를 n 순서로 모두 출력하고, F(20)과 F(25)에서는 counter.clear()로 비운 뒤 전체 호출 수만 더해 출력합니다.

counter = {}


def fib_naive(n):
    counter[n] = counter.get(n, 0) + 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


print(fib_naive(5), dict(sorted(counter.items())))
counter.clear()
fib_naive(20)
print(sum(counter.values()))
counter.clear()
fib_naive(25)
print(sum(counter.values()))

5 {0: 3, 1: 5, 2: 3, 3: 2, 4: 1, 5: 1}
21891
242785

F(5)를 한 번 구하는 동안 F(3)을 두 번, F(2)를 세 번, F(1)을 다섯 번 계산했습니다. F(5)는 F(4)와 F(3)을 부르는데, F(4)가 다시 F(3)을 부르므로 F(3)이 두 번 계산되고, 그 아래로 내려갈수록 같은 계산이 더 많이 겹치기 때문입니다. 전체 호출 수는 F(20)에서 2만 번, F(25)에서 24만 번을 넘어, n이 5 늘 때마다 약 11배씩 늘어납니다. 호출 수는 F(n) 자신과 같은 비율로 늘어나는데, F(n)은 n이 하나 늘 때마다 약 1.618배가 되므로 호출 수도 n에 대해 지수적으로 늘어납니다.

메모이제이션: 구한 답을 기억한다

F(3)은 몇 번을 계산해도 같은 값이므로, 처음 계산할 때 적어 두고 다음부터는 적어 둔 값을 쓰면 됩니다. 함수가 구한 답을 인자별로 저장해 두었다가 같은 인자로 다시 불리면 저장한 값을 돌려주는 방법을 메모이제이션(memoization)이라고 합니다. 저장하는 곳은 인자를 키로 하는 딕셔너리면 충분합니다.

calls = 0


def fib_memo(n, memo=None):
    global calls
    calls += 1
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


print(fib_memo(20), calls)

6765 39

같은 F(20)을 구하는 데 호출이 21891번에서 39번으로 줄었습니다. F(2)부터 F(20)까지 19개의 값은 각각 한 번만 계산되고, 나머지 호출은 이미 저장된 값을 꺼내거나 기저 사례에서 바로 돌아오기 때문입니다. memo를 기본값 {}로 두지 않고 None에서 새로 만드는 이유는 스택과 깊이 우선 탐색 DFS에서 본 것과 같습니다.

Python의 표준 라이브러리 functools에는 이 일을 대신해 주는 cache가 있습니다. 함수 정의 위에 @cache를 붙이면, 함수가 같은 인자로 불렸을 때 저장해 둔 결과를 돌려주도록 바뀝니다. @로 시작하는 이 줄을 데코레이터(decorator)라 하며, 함수에 기능을 덧입히는 문법입니다.

from functools import cache


@cache
def fib_cached(n):
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)


print(fib_cached(90))

2880067194370816120

메모이제이션을 쓴 재귀는 큰 문제에서 시작해 필요한 작은 문제를 그때그때 부르므로, 위에서 아래로 가는 방식(top-down)이라고 부릅니다. 계산이 필요한 상태만 계산한다는 것이 장점입니다. 단점은 호출 스택입니다. 처음 F(n)을 구할 때는 F(n - 1), F(n - 2), …로 기저 사례까지 내려가는 호출이 쌓이므로 깊이가 n에 비례하고, fib_cached(5000)은 Python의 재귀 깊이 한도에 걸려 RecursionError가 납니다.

아래에서부터 표를 채우기

반대로 작은 수부터 차례로 계산해 표를 채우는 방식을 아래에서 위로 가는 방식(bottom-up)이라고 합니다. F(0)과 F(1)을 적고, F(2)부터 F(n)까지 바로 앞 두 칸을 더해 채우면 됩니다. 각 칸은 앞의 두 칸만 읽으므로, 작은 쪽부터 채우는 순서가 필요한 값을 늘 먼저 준비해 줍니다.

그런데 F(k)를 계산할 때는 F(k - 1)과 F(k - 2)만 필요하고 그보다 앞의 칸은 다시 쓰지 않습니다. 그렇다면 표 전체를 둘 필요 없이 마지막 두 값만 변수 두 개에 들고 있으면 됩니다. before와 current가 차례로 F(k)와 F(k + 1)을 담도록 하고, 한 번 반복할 때마다 한 칸씩 앞으로 옮깁니다.

def fib_iter(n):
    before, current = 0, 1
    for _ in range(n):
        before, current = current, before + current
    return before


print([fib_iter(n) for n in range(10)])
print(fib_iter(90), len(str(fib_iter(1000))))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
2880067194370816120 209

k번 반복한 뒤 before는 F(k), current는 F(k + 1)이라는 사실이 반복 내내 유지되므로, n번 반복한 뒤의 before가 F(n)입니다. 이 방식은 재귀를 쓰지 않으므로 F(1000)처럼 큰 n도 문제없이 계산하며, F(1000)은 209자리 수입니다.

before, current = current, before + current는 한 줄에서 두 변수를 동시에 바꾸는 문장입니다. Python은 오른쪽의 current와 before + current를 모두 계산한 뒤에 왼쪽 두 변수에 넣습니다. 이것을 두 줄로 나누어 쓰면 결과가 틀어집니다.

def fib_wrong(n):
    before, current = 0, 1
    for _ in range(n):
        before = current
        current = before + current
    return before


print([fib_wrong(n) for n in range(8)])

[0, 1, 2, 4, 8, 16, 32, 64]

첫 줄에서 before가 이미 current로 바뀌었으므로, 둘째 줄의 before + current는 원래의 두 값이 아니라 current + current가 됩니다. 그래서 매번 두 배가 되어 2의 거듭제곱이 나옵니다. 여러 변수를 서로의 이전 값으로 함께 바꿀 때는 동시 대입을 쓰거나, 이전 값을 임시 변수에 먼저 저장해야 합니다.

두 방식의 비교

피보나치 수처럼 모든 작은 상태가 결국 필요하고 계산 순서가 분명한 문제는 아래에서부터 채우는 편이 단순하고 안전합니다. 상태가 많지만 실제로 필요한 것은 일부뿐이거나, 계산 순서를 미리 정하기 어려운 문제에서는 메모이제이션이 편합니다. 두 방식은 같은 점화식을 계산 순서만 다르게 따르는 것이라, 한쪽으로 만든 답을 다른 쪽으로 바꾸어 쓰는 일도 흔합니다.

비용

두 방식 모두 덧셈을 약 n번 합니다. 덧셈 한 번을 상수 시간으로 보면 시간은 O(n)이고, 공간은 메모이제이션이 O(n), 두 변수 방식이 O(1)입니다. 다만 피보나치 수는 매우 빨리 커져서 F(n)의 이진 자릿수는 약 0.694n입니다. F(1000)만 해도 694비트입니다. 이렇게 큰 정수의 덧셈은 자릿수에 비례하는 시간이 들므로, 자릿수까지 따지면 전체 시간은 O(n²)에 가깝고, 두 변수 방식도 수 자체를 담는 데 O(n)비트가 필요합니다. 어떤 연산을 한 단계로 셀지는 분석하기 전에 정해 두어야 하는 약속입니다.

더 깊이: 행렬 거듭제곱으로 더 빠르게

피보나치 수는 n번 덧셈하지 않고도 구할 수 있습니다. 2 × 2 행렬 [[1, 1], [1, 0]]을 n번 곱하면 결과의 오른쪽 위 칸이 F(n)이 된다는 성질이 있습니다. 한 번 곱할 때마다 (F(k + 1), F(k))를 (F(k + 2), F(k + 1))로 한 칸씩 옮기는 효과가 있기 때문입니다. 그리고 거듭제곱은 n을 절반씩 줄여 가며 계산할 수 있습니다. 예를 들어 M의 8제곱은 M을 제곱하고, 그것을 다시 제곱하고, 한 번 더 제곱하면 되므로 곱셈 세 번이면 됩니다.

def mat_mult(a, b):
    return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
            [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]


def mat_pow(m, n):
    result = [[1, 0], [0, 1]]
    while n > 0:
        if n % 2 == 1:
            result = mat_mult(result, m)
        m = mat_mult(m, m)
        n //= 2
    return result


def fib_matrix(n):
    return mat_pow([[1, 1], [1, 0]], n)[0][1]


print([fib_matrix(n) for n in range(10)], fib_matrix(90))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] 2880067194370816120

mat_pow는 n을 이진수로 보고, 1인 자리마다 그 자리에 해당하는 제곱을 결과에 곱합니다. 반복마다 n이 절반으로 줄므로 행렬 곱셈은 O(log n)번입니다. 행렬 곱셈 자체는 11장의 행렬의 모양·덧셈·곱셈에서 자세히 다룹니다. 큰 정수 곱셈의 비용까지 따지면 이야기가 더 복잡해지지만, n이 아주 클 때는 이 방법이 덧셈을 n번 하는 방법보다 훨씬 빠릅니다.

정리

• 피보나치 수를 정의대로 재귀로 계산하면 같은 작은 수를 여러 번 다시 계산해 호출 수가 n에 대해 지수적으로 늘어납니다.
• 메모이제이션은 구한 답을 인자별로 저장해 같은 계산을 한 번만 하며, functools.cache로 간단히 쓸 수 있습니다. 위에서 아래로 가는 방식이라 재귀 깊이가 n에 비례합니다.
• 아래에서부터 채우는 방식은 작은 수부터 차례로 계산하며, 피보나치 수는 앞의 두 값만 있으면 되므로 변수 두 개로 충분합니다.
• 두 변수를 서로의 이전 값으로 바꿀 때는 동시 대입을 써야 하며, 한 줄씩 나누어 쓰면 이미 바뀐 값을 쓰게 됩니다.
• 덧셈을 상수로 보면 O(n)이지만, F(n)의 자릿수가 n에 비례하므로 큰 n에서는 큰 정수 연산의 비용도 따져야 합니다.

연습 문제

1. 반복을 여섯 번 한 뒤

fib_iter의 반복을 여섯 번 한 뒤 before와 current의 값은 무엇인가요?

2. 캐시를 붙이면 재귀 깊이 문제도 사라질까

@cache를 붙인 fib_cached로 fib_cached(5000)을 처음 계산하면 어떻게 될까요? 캐시는 무엇을 줄여 주고 무엇을 줄여 주지 못하나요?

3. 계단 오르기

계단을 한 번에 한 칸 또는 두 칸씩 오를 수 있을 때, n칸짜리 계단을 오르는 방법의 수 W(n)을 구하는 점화식을 세우세요. W(1)부터 W(7)까지는 얼마인가요?

다음 글 LCS·부분 수열·표와 복원에서는 상태가 두 개의 수로 정해지는 2차원 표를 채우고, 표를 거꾸로 따라가 실제 답을 복원합니다.