카테고리 없음

피보나치 수열로 마스터하는 DP: Top-down과 Bottom-up 비교

kguidebook0001 2026. 4. 11. 07:15

수학적 아름다움을 간직한 피보나치 수열($1, 1, 2, 3, 5, 8, \dots$)은 컴퓨터 과학에서 알고리즘의 효율성을 설명하는 가장 완벽한 예제입니다. 단순히 재귀로 구현하면 지수 시간 복잡도($O(2^n)$)에 빠져버리는 이 문제를, 동적 계획법(DP)은 어떻게 선형 시간($O(n)$)으로 해결하는 것일까요? 본 포스팅에서는 피보나치 수열을 통해 하향식(Top-down)과 상향식(Bottom-up) 구현의 실체를 파악하고, 각 방식의 메모리 사용과 실행 속도 차이를 2,500자 이상의 밀도 있는 텍스트로 분석해 보겠습니다.

1. 단순 재귀의 한계와 지수 시간의 공포

피보나치 수열의 정의는 $F(n) = F(n-1) + F(n-2)$입니다. 이를 그대로 재귀 함수로 코딩하면, $F(50)$만 구하려 해도 우주의 나이만큼 시간이 걸릴 수 있습니다. 왜 그럴까요? 바로 중복 계산 때문입니다. $F(5)$를 구하기 위해 $F(4)$와 $F(3)$을 부르고, $F(4)$는 다시 $F(3)$과 $F(2)$를 부릅니다. 이 과정에서 $F(3)$은 여러 번 호출되며, $n$이 커질수록 호출 횟수는 기하급수적으로 증가합니다. 이것이 바로 우리가 DP를 배워야 하는 결정적인 이유입니다.

2. 하향식 접근(Top-down): 메모이제이션의 마법

하향식은 우리가 문제를 바라보는 방식과 가장 닮아 있습니다. "$F(n)$을 구하고 싶어? 그럼 $F(n-1)$과 $F(n-2)$를 가져와"라고 명령하는 식입니다. 이때 메모이제이션 배열을 도입하면, 한 번 구한 $F(3)$의 값을 저장해두었다가 다음 호출 때 즉시 반환합니다.

2-1. 하향식 코드의 특징

가독성이 좋고 점화식을 그대로 옮겨놓은 듯한 형태를 가집니다. 필요한 값만 계산하기 때문에 불필요한 연산을 피할 수 있다는 장점이 있습니다. 다만 파이썬과 같은 언어에서는 재귀 호출 깊이 제한(Recursion Limit)에 걸릴 수 있어, 설정값을 변경하거나 스택 구조를 고려해야 합니다.

3. 상향식 접근(Bottom-up): 타뷸레이션의 안정성

상향식은 작은 값부터 벽돌을 쌓아 올리듯 계산하는 방식입니다. $F(1)$과 $F(2)$를 먼저 구하고, 이를 이용해 $F(3)$을 구하며 점진적으로 목표치까지 나아갑니다. 반복문(for loop)을 사용하기 때문에 실행 속도가 매우 안정적이며 예측 가능합니다.

3-1. 공간 복잡도 최적화 팁

상향식 피보나치 구현 시, 사실 모든 배열의 값이 필요하지는 않습니다. $F(n)$을 구하기 위해 바로 직전의 두 값만 알면 되기 때문입니다. 배열 전체를 유지하는 대신 변수 두 개만 사용하여 공간 복잡도를 $O(n)$에서 $O(1)$로 줄이는 테크닉은 실무에서 매우 유용하게 쓰입니다.

4. 어떤 방식을 선택해야 하는가?

이론적으로 두 방식의 시간 복잡도는 $O(n)$으로 동일합니다. 하지만 시스템의 환경에 따라 선택이 달라집니다.

  • Top-down: 문제의 구조가 복잡하여 점화식을 직관적으로 구현하고 싶을 때, 혹은 전체 상태 중 일부만 탐색해도 될 때 추천합니다.
  • Bottom-up: 시스템의 안정성이 중요할 때, 재귀의 오버헤드를 피하고 싶을 때, 모든 상태값을 채워야 할 때 강력히 추천합니다.

# Top-down (Memoization)
memo = [0] * 101
def fibo_top(n):
    if n <= 2: return 1
    if memo[n] != 0: return memo[n]
    memo[n] = fibo_top(n-1) + fibo_top(n-2)
    return memo[n]

# Bottom-up (Tabulation)
def fibo_bottom(n):
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
[피보나치와 DP 핵심 요약]
1. 문제 해결: 단순 재귀의 $O(2^n)$ 복잡도를 DP를 통해 $O(n)$으로 개선합니다.
2. Top-down: 재귀와 기록(Memoization)을 사용하며 직관적인 설계가 가능합니다.
3. Bottom-up: 반복문과 상향식 누적(Tabulation)을 사용하며 안정적인 성능을 보장합니다.