[파이썬 알고리즘] Ch 7-1. 피보나치 수열과 동적 계획법

Posted Dec 16, 2025

By JaeJin Hwang

8 min read

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021

동적 계획법(Dynamic programming)은 1950년대 미국 수학자 벨맨(Richard Bellman)이 만든 용어로, 다단계 의사 결정 프로세스를 최적화하는 일반적인 방법으로 처음 소개되었다.

큰 문제를 작은 문제로 나누고, 그 결과를 저장해 두었다가 재사용하는 문제 해결 기법이다. 여기서 핵심은 같은 부분 문제를 다시 풀지 않도록 하는 것이다. 따라서, 넓게 보면 공간으로 시간 벌기 전략에 포함 될 수도 있다.

피보나치 수열(Fibonacci numbers)은 다음과 같이 순환적으로 정의된다. (분할 정복)

\[fibo(n) =\begin{cases}n & n \leq 1\\fibo(n-2) \ + \ fibo(n-1) & otherwise \end{cases}\]

이와 같이 분할 정복 기법을 이용해서 코드를 작성하게 되면 같은 계산을 중복해서 계산하는 심각한 문제가 발생한다. 예를 들어, $fibo(6)$을 구하기 위해서 $fibo(1)$이 8번이나 호출되어야 하는데, 이것은 한 번 해결한 문제를 8번이나 다시 풀어야 하는 것을 의미한다. → $O(2^n)$

< 동적 계획법의 구현 방법 >

하향식(top-down) 방법: 메모이제이션(memoization)
상향식(bottom-up) 방법: 테이블화(tabulation)

1. 메모이제이션을 이용한 피보나치 수열

문제를 풀 때마다 이미 풀린 문제인지를 먼저 확인한다.
풀린 문제이면 저장된 답을 이용하고,
풀리지 않은 문제이면 그 문제를 풀고 답을 다시 저장한다.

$e.g.$
아래 그림은 메모이제이션을 이용한 피보나치 수열 $fib(6)$을 구하는 과정을 보여준다.

한 번 풀린 문제는 다시 풀지 않고 그 답을 이용하기 때문에 회색 박스들은 더 이상 실행할 필요가 없다.
따라서, 모든 부분 문제들은 한 번씩 풀면 된다.

< 계산 과정 >

해당 알고리즘은 여전히 재귀 구조를 사용하고 있다.
전역 변수인 mem은 크기가 $n+1$인 리스트로, mem[k]는 k번째 피보나치 수열 값을 의미한다.
이 함수를 호출하기 전에 먼저 mem의 모든 항목들을 None으로 반드시 초기화되어 있어야 한다.

  
# 피보나치 수열 함수(메모이제이션)
def fibo_dp_mem(n):
    if(mem[n] == None):     # mem[n]에 값이 저장되지 않은 경우에만 계산을 실행
        if n < 2:               # base case인 경우 (0 또는 1)
            mem[n] = n      
        else:                   # 아직 계산되지 않은 경우 (재귀 호출)
            mem[n] = fibo_dp_mem(n-1) + fibo_dp_mem(n-2)
    
    return mem[n]


# 메모이제이션 방식 테스트
n = 8
mem = [None] * (n+1)
print("동적 계획(메모이제이션): Fibonacci(%d) = "%n, fibo_dp_mem(n))

  
# 출력 결과
동적 계획(메모이제이션): Fibonacci(8) =  21

시간 복잡도 : $O(n)$

모든 부분 문제를 정확히 한 번씩 처리하고, 이러한 부분 문제의 수가 $n$개 이다.

공간 복잡도 : $O(n)$

답을 저장하기 위한 테이블 mem이 추가적으로 필요하고, 크기는 $n+1$ 이다.

2. 테이블화를 이용한 피보나치 수열

결과를 저장할 테이블을 면저 만든다.
다음으로 답이 이미 알려진 단순한 상황, 즉 기반 상황(base case)에 대한 테이블 항목을 먼저 채우고,
이들을 바탕으로 테이블을 채워서 올린다.

$e.g.$
아래 그림은 테이블화를 이용한 피보나치 수열 $fib(6)$을 구하는 과정을 보여준다.

테이블화를 위해서는 먼저 결과를 저장할 테이블(table)이 필요한데, 만약 $fib(n)$을 구하려면 크기가 $n+1$ 인 테이블이 필요하다. 예를 들어, $fib(6)$을 구하려면 $fib(0)$ 부터 $fib(6)$ 까지의 결과를 저장해야 하기 때문이다.

< 계산 과정 >

계산은 기반 상황(base case)부터 시작된다. 먼저, $fib(0)$과 $fib(1)$의 답을 테이블에 저장한다.
다음부터는 남아있는 가장 작은 부분 문제부터 순서적으로 해을 구하고 테이블에 저장하는 과정을 반복한다.
이는 문제 $fib(6)$을 구할 때 까지 진행된다.

  
# 피보나치 수열 함수(테이블화)
def fibo_dp_tbl(n):
    f = [None] * (n+1)      # 테이블 생성
    f[0] = 0                # 기반 상황 처리
    f[1] = 1                # 기반 상황 처리

    for i in range(2, n+1):     # 상향식으로 계산 
        f[i] = f[i-1] + f[i-2]  # 부분 문제들을 해결하고 저장
    
    return f[n]     # 결과 반환


# 테이블화 방식 테스트
n = 8
print("동적 계획(테이블화): Fibonacci(%d) = "%n, fibo_dp_tbl(n))

  
# 출력 결과
동적 계획(테이블화): Fibonacci(8) =  21

시간 복잡도 : $O(n)$

이 알고리즘은 재귀 호출을 사용하지 않고, 7행에서 $n$번 반복하는 하나의 루프를 사용하므로 시간 복잡도는 명백히 $O(n)$ 이다.

공간 복잡도 : $O(n)$

메모이제이션과 동일하게 계산 결과를 저장하기 위한 테이블이 필요하고, 크기는 $n+1$ 이다.

메모이제이션과 테이블화를 이용한 피보나치 수열 알고리즘은 모두 시간 복잡도가 $O(n)$으로, 분할 정복 알고리즘의 $O(2^n)$에 비해 월등한 성능을 보인다. 그러나 추가적인 메모리가 필요하다는 단점이 있다.

algorithm

This post is licensed under CC BY 4.0 by the author.

1. 메모이제이션을 이용한 피보나치 수열

2. 테이블화를 이용한 피보나치 수열

Trending Tags