[알고리즘] 파이썬으로 피보나치 수열 구현하기 | 동적계획법(Dynamic Programming) 예시

동적계획법

동적계획법(Dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리, 단위별로 문제를 해결하여 전체 문제를 푸는 방법입니다. 동적계획법의 원리와 구현 방식은 다음과 같다고 합니다. [1]

 

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제들이 반복되고, 작은 문제들의 결과 값은 항상 같아야 한다.
3. 작은 문제들은 한 번만 계산해 DP 테이블(Dynamic Programming Table)에 저장합니다. 작은 문제들의 답을 활용할 때는 DP 테이블에서 가져옵니다. (Memoization)
4. 이를 Top-down과 Bottom-up 방식 중 하나로 구현합니다.

이렇게만 보면 이해가 어렵기 때문에 대표적인 동적계획법 문제인 피보나치 수열 구현을 통해 살펴보겠습니다.

 

피보나치 구현

과정 1

피보나치 수열은 다음 항이 이전 두 항의 합으로 이뤄진 수열입니다. 그리고 두 개의 항 역시 그 이전의 항들의 합들로 이뤄지는 점화식 형태이기 때문에 작은 문제들로 분리할 수 있습니다. 

과정 2

점화식 형태로 나타낼 수 있다는 것은 작은 문제들이 반복되고, 그 구조가 비슷함을 의미합니다. 따라서, 피보나치 문제는 동적계획법을 통해 접근이 가능합니다.

피보나치 수열 점화식 [2]

과정 3

메모이제이션(Memoization)은 어떻게 구현해야 할까요? 처음에 주어지는 두 항을 저장하고 그 다음부터는 점화식에 따라 계산되는 값을 저장해주면 될 것입니다.

과정 4

피보나치 수열은 비교적 간단한 코드이기 때문에 바로 비교해보도록 하겠습니다. 우선 Top-down 방식은 주로 재귀 함수를 통해 구현하며, 그렇기 때문에 가독성이 좋습니다. 다만, 재귀함수를 쓰는만큼 반복해야 하는 숫자가 증가할 경우 런타임 에러를 발생시킬 우려가 있습니다.

 

import sys
input = sys.stdin.readline
N = int(input())
D = [-1] * (N+1)
D[0] = 0
D[1] = 1

def fibo(n):
    if D[n] != -1: # 계산했으면 제외
        return D[n]
    D[n] = fibo(n-1) + fibo(n-2)
    return D[n]

fibo(N)
print(D[N])

 

반면, Bottom-up 방식은 반복문을 통해 아래에서부터 채워가는 방식을 사용합니다. 

 

import sys
input = sys.stdin.readline
N = int(input())
D = [-1] * (N+1)
D[0] = 0
D[1] = 1

for i in range(2, N+1):
    D[i] = D[i-1] + D[i-2]
    
print(D[N])

 

참고자료

[1] Do it! 알고리즘 코딩 테스트 : 파이썬편

[2] https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98