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

같은 작은 문제를 반복 호출하는 재귀를 줄일 수 있습니다. 목표는 메모이제이션과 아래에서 채우기의 차이, 숫자 크기와 공간 설명을 구분하는 것입니다. 재귀와 DP 상태를 복습하세요.

개념과 약속

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)입니다. 저장 없는 재귀는 F(n-2) 같은 상태를 여러 갈래에서 다시 구해 호출 수가 지수적으로 늘어납니다. 메모이제이션은 호출된 상태의 답을 캐시에 보존합니다. 여기 lru_cache는 내부 solve 함수의 정수 인자별 결과를 보존하며 함수 호출마다 새 캐시를 만듭니다.

반복 방식은 0부터 상태를 올려 계산합니다. 다음 항에는 이전 두 항만 필요하므로 표 전체 대신 두 변수만 유지할 수 있습니다. before, current = current, before + current는 오른쪽 둘을 이전 값으로 먼저 계산한 뒤 함께 대입합니다. 하나씩 덮어쓰면 잘못된 항을 더할 수 있습니다.

손으로 상태 추적하기

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

from functools import lru_cache

def fibonacci_memo(n):
    if n < 0:
        raise ValueError("nonnegative n required")
    @lru_cache(maxsize=None)
    def solve(k):
        return k if k < 2 else solve(k - 1) + solve(k - 2)
    return solve(n)


def fibonacci_table(n):
    if n < 0:
        raise ValueError("nonnegative n required")
    before, current = 0, 1
    for _ in range(n):
        before, current = current, before + current
    return before


print([fibonacci_memo(n) for n in range(8)])
print([fibonacci_table(n) for n in range(8)])
print(fibonacci_table(20))

실행 결과:

[0, 1, 1, 2, 3, 5, 8, 13]
[0, 1, 1, 2, 3, 5, 8, 13]
6765

왜 맞고 언제 끝나는가

기저 두 항은 정의와 맞습니다. 이미 구한 이전 두 항이 맞으면 합도 다음 정의에 맞습니다. 반복 k번 뒤 두 변수는 F(k),F(k+1)라는 불변조건을 유지합니다. 재귀는 인자가 줄고 캐시로 같은 상태를 다시 풀지 않습니다. 다만 Python 호출 깊이 제한은 남아 큰 n에는 반복 방식이 안전합니다.

비용과 적용 범위

두 방식 모두 O(n) 덧셈입니다. 메모이제이션은 O(n) 상태·호출 깊이를 쓰고 반복은 변수 개수가 O(1)입니다. 하지만 F(n)의 비트 수는 n에 비례하므로 반복의 실제 숫자 저장 비트 공간까지 O(1)이라고 주장하지 않습니다. 큰 정수 덧셈을 상수로 보는 모델도 별도로 밝힙니다.

스스로 풀어 보기

1. 반복 6번 뒤 before와 current는 무엇인가요?
2. 캐시만 추가하면 재귀 깊이 문제도 없어지나요?

힌트

1. F(6),F(7)을 찾습니다.
2. 처음 F(n)을 구할 때 호출이 내려가는 경로는 남습니다.

해설

1. 8과 13입니다.
2. 없어지지 않습니다. 중복 분기는 줄지만 n에서 기저 사례로 내려가는 호출 깊이는 여전히 O(n)입니다.

흔한 오해

동적 계획법이 반드시 모든 표를 저장해야 하는 것은 아닙니다. 필요한 이전 상태가 제한적이면 저장을 줄일 수 있습니다. 복원까지 필요할 때는 기록을 더 남겨야 할 수 있습니다.

복습과 다음 연결

다음 LCS에서는 길이의 표뿐 아니라 실제 문자열을 되돌아 찾습니다. 캐시 API는 functools 공식 문서에 있습니다.