[정글 베이직26] 동적 프로그래밍 - 피보나치 수열 (하향식 / Top-down)

Dynamic Programming · Fibonacci · Top-down · Memoization

동적 프로그래밍 - 피보나치 수열 (하향식 / Top-down)

재귀 피보나치를 메모이제이션으로 최적화해서 O(2^n) → O(n) 으로 바꾸는 대표적인 DP 입문 예제

문제 한눈에 보기

목표	메모이제이션을 사용해 n번째 피보나치 수를 효율적으로 계산하기
입력	정수 n
출력	n번째 피보나치 수
예시	n = 10 이면 결과는 55
핵심	이미 계산한 값을 memo 에 저장하고 재사용한다

핵심 1

피보나치 정의는 fib(n) = fib(n-1) + fib(n-2) 이다. 이 정의가 틀리면 전체 코드가 무너진다.

핵심 2

메모이제이션은 memo 확인 → 없으면 계산 → 저장 → 반환 순서로 동작해야 한다.

핵심 3

재귀 호출마다 같은 memo 딕셔너리를 계속 넘겨야 계산 결과를 공유할 수 있다.

동적 프로그래밍이란?

동적 프로그래밍(DP)은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장해서 다시 사용하는 방식이다.

DP가 잘 맞는 문제는 보통 두 가지 성질을 가진다. 첫째, 최적 부분 구조. 둘째, 중복 부분 문제다.

피보나치는 같은 값이 계속 반복해서 등장하므로 DP 설명용 예제로 가장 많이 쓰인다.

하향식(Top-down) 방식이란?

큰 문제부터 시작해서, 필요한 작은 문제를 재귀적으로 호출하며 내려가는 방식이다.

fib(10) → fib(9) + fib(8) → fib(8) + fib(7) + fib(7) + fib(6) → ...

이 과정에서 이미 계산한 값을 memo에 저장해 두면, 같은 문제가 다시 나왔을 때 다시 계산하지 않고 바로 꺼내 쓸 수 있다. 이것이 메모이제이션(Memoization)이다.

처음 코드에서 잘못되기 쉬운 부분

실수	왜 문제인가?
return fibonacci_memo(n-1) + n	피보나치 정의가 아니다. 올바른 정의는 fib(n-1) + fib(n-2) 이다.
memo 확인보다 재귀 호출이 먼저 옴	이미 저장된 값을 쓰기 전에 계산이 끝나버려 메모이제이션 효과가 사라진다.
계산 후 memo[n] 에 저장하지 않음	다음에 같은 n이 등장해도 또 계산해야 한다.
재귀 호출에 memo 를 넘기지 않음	같은 딕셔너리를 공유하지 못해 캐시 재사용이 깨질 수 있다.

최종 코드

def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n == 0:
        memo[0] = 0
        return 0
    if n == 1:
        memo[1] = 1
        return 1

    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

한 줄씩 자세히 설명

줄	코드	설명
1	def fibonacci_memo(n, memo=None):	n번째 피보나치 수를 구하는 함수다. memo는 이미 계산한 값을 저장하는 딕셔너리다.
2-3	if memo is None: memo = {}	처음 호출일 때만 빈 딕셔너리를 만든다. 이후 재귀 호출에서는 같은 memo를 계속 전달한다.
5-6	if n in memo: return memo[n]	이미 계산한 값이면 바로 반환한다. 이 부분이 메모이제이션의 핵심이다.
8-10	if n == 0: memo[0] = 0 return 0	피보나치의 기저 조건이다. fib(0)은 0이다.
11-13	if n == 1: memo[1] = 1 return 1	또 다른 기저 조건이다. fib(1)은 1이다.
15	memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)	아직 계산되지 않았다면 재귀로 구한다. 중요한 점은 같은 memo를 두 재귀 호출에 모두 넘긴다는 것이다.
16	return memo[n]	저장한 값을 반환한다. 이후 같은 n이 다시 나오면 곧바로 꺼내 쓸 수 있다.

왜 O(n)이 되는가?

일반 재귀는 같은 값을 계속 다시 계산한다. 예를 들어 fib(5)를 구할 때 fib(3), fib(2)가 여러 번 반복 호출된다.

일반 재귀 fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) ... ... ... ...

하지만 메모이제이션을 쓰면 fib(0)부터 fib(n)까지 각 값은 딱 한 번만 계산된다.

그래서 시간 복잡도는 O(n) 이 된다. 값을 저장하는 memo 딕셔너리와 재귀 호출 스택 때문에 공간 복잡도도 O(n) 이다.

계산 과정 예시: fib(5)

단계	설명
1	fib(5)를 계산하려고 한다.
2	fib(4), fib(3)을 재귀로 계산한다.
3	fib(3), fib(2), fib(1), fib(0)을 내려가며 계산하고 memo에 저장한다.
4	다시 fib(3)이나 fib(2)가 필요해지면, 계산하지 않고 memo에서 바로 꺼낸다.
5	중복 계산이 사라져 훨씬 빠르게 끝난다.

자주 헷갈리는 포인트

헷갈리는 점	정리
왜 base case 아래 TODO가 비어 보이나?	원래 있던 pass 는 임시 표시일 뿐이다. 실제 코드가 들어갔다면 삭제해도 되고, 남아 있어도 아래 코드가 있으면 큰 문제는 없다.
왜 memo(n) 이 아니라 memo[n] 인가?	딕셔너리에 값을 저장하거나 꺼낼 때는 대괄호를 사용한다. 소괄호는 함수 호출 문법이다.
왜 memo 를 재귀 호출에 넘겨야 하나?	같은 저장소를 공유해야 이미 계산한 값을 재사용할 수 있기 때문이다.
왜 memo 체크를 먼저 해야 하나?	계산보다 먼저 확인해야 이미 저장된 값을 즉시 반환할 수 있다. 그래야 중복 계산이 사라진다.

시간복잡도

각 값 fib(0) ~ fib(n)을 한 번씩만 계산하므로 O(n)

공간복잡도

memo 딕셔너리와 재귀 호출 스택 때문에 O(n)

핵심 요약

• 피보나치 정의는 fib(n) = fib(n-1) + fib(n-2) 이다.
• 메모이제이션의 흐름은 확인 → 계산 → 저장 → 반환 이다.
• 같은 memo 딕셔너리를 재귀 호출마다 넘겨야 한다.
• 일반 재귀는 O(2^n), 메모이제이션을 쓰면 O(n)으로 줄어든다.

한 문장 정리

이 문제의 본질은 피보나치 값을 재귀로 구하되, 한 번 계산한 값은 memo에 저장해서 다시 계산하지 않는 데 있다.