다이나믹 프로그래밍

 

DP 사용조건

- 큰 문제를 작은 문제로 나눌 수 있음

- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함

 

 

탑다운(Top-Down) 방식

- 작은 문제를 재귀적으로 해결

d = [0] * 100 # 한 번 계산된 결과를 memoization하기 위한 list 초기화

def fibo(x): # 피보나치 함수를 재귀함수로 구현 (탑다운)
    if x == 1 or x == 2:
        return 1
    
    if d[x] != 0: # 이미 계산한 적 있는 문제라면 그대로 반환
        return d[x]

    d[x] = fibo(x - 1) + fibo(x - 2) # 아직 계산하지 않은 문제라면 점화식에 따라 결과 반환

    return d[x]

print(fibo(99))

 

 

보텀업(Bottom-Up) 방식

- 먼저 계산했던 값 이용

d = [0] * 100 # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화

d[1] = 1 # 첫번째 피보나치 수 
d[2] = 1 # 두번째 피보나치 수
n = 99 

for i in range(3, n+1): # 피보나치 함수를 반복문으로 구현 (보텀업)
    d[i] = d[i-1] + d[i-2]
    
print(d[n])

 

 

파이썬 재귀 제한 완화

import sys

sys.setrecursionlimit(10**6)

 

 

💡 Tip

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현할 것