동적 계획법
작성 완료
- 다이나믹 프로그래밍 참고: 동적 계획법
- 다이나믹 프로그래밍((Dynamic Programming)으로도 불림
- 큰 문제를 작은 문제로 나눠서 푸는 방법
- 분할 정복과 유사하지만...
| 동적 계획법 | 분할 정복 | |
|---|---|---|
| 공통점 | 큰 문제를 작은 문제로 나눠서 해결 | 큰 문제를 작은 문제로 나눠서 해결 |
| 차이점 | 작은 문제가 반복됨 | 작은 문제가 반복되지 않음 |
- 나중에 분할 정복에 대해서도 다뤄보자
1. 작은 문제들의 반복
2. 같은 문제는 구할 때마다 정답이 같음
- 모든 작은 문제는 단 한번만 풀어야 함
- 정답을 구한 작은 문제는 어딘가에 저장
- 큰 문제를 해결할 때 미리 구한 작은 문제의 정답을 사용
- 피보나치 수열을 다이나믹 프로그래밍으로 구현해보자
- 큰 문제를 해결할 때 작은 문제가 해결되지 않았으면 작은 문제를 해결하여 큰 문제를 해결
- 재귀 함수로 구현하는 경우가 Top-down 방법
- 메모이제이션 기법 사용 ---> 미리 구한 작은 문제의 정답을 어딘가에 저장
- 단순 재귀 함수로 구현한 피보나치 함수의 시간 복잡도는 $T(n) = T(n-1) + T(n-2) + C$이다
- 하지만 Top-down 방법을 사용한 피보나치 함수의 시간 복잡도는 $T(n) = T(n-1) + C$이다
- 왜냐하면 메모이제이션을 통해 피보나치 함수값을 $T(n-1)$을 재귀호출 하면서 미리 구해놨기 때문에
- $T(n-2)$에서는 재귀호출이 일어나지 않아 상수시간만 소요된다
fibonacci = {0: 0, 1: 1} # 메모이제이션을 위한 딕셔러니 선언
def fibo_top_down(n):
if n in fibonacci:
return fibonacci[n]
fibonacci[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2)
return fibonacci[n]
fibo_top_down(10)
- 작은 문제부터 차근차근 해결하여 큰 문제를 해결
- 반복문 사용
def fibo_bottom_up1(n):
if n <= 1:
return n
fir_fibo = 0
sec_fibo = 1
for _ in range(n - 1):
next_fibo = fir_fibo + sec_fibo # 2번째 피보나치 값 = 0번째 피보나치 값 + 1번째 피보나치 값 (n번째 피보나치 값 = n-2번째 피보나치 값 + n-1번째 피보나치 값)
fir_fibo = sec_fibo # 0번째 피보나치 값을 1번째 피보나치 값으로 업데이트
sec_fibo = next_fibo # 1번째 피보나치 값을 2번째 피보나치 값으로 업데이트
# 다시 for문 시작으로 돌아가서 1번째 피보나치 값과 2번째 피보나치 값을 통해 3번째 피보나치 값을 구함 (이를 n-1번 반복)
# for 문의 역할은 점화식을 통해 0번째와 1번째의 피보나치 값을 가지고 n번째의 피보나치 값을 구한다
return next_fibo
fibo_bottom_up1(10)
- 또 다른 방법
- 미리 dp라는 list를 생성
x = 100 # 문제 조건에 맞춰서
dp = [-1] * x # 리스트 초기화
def fibo_bottom_up2(n):
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
fibo_bottom_up2(10)
- bottom-up 방식으로 구현한 위의 두개 코드의 차이점은?
- fibo(9)와 fibo(10)을 구할 때 처음 코드는 fibo_bottom_up1(9)과 fibo_bottom_up1(10) 총 함수를 2번 사용
- 사실 fibo_bottom_up1(10)을 계산했다면 fibo_bottom_up1(9)도 당연히 알지만 각각을 따로 두 번 구했다
- 첫 번째 코드의 경우 다이나믹 프로그래밍은 이미 구한 작은 문제 정답은 또 구하지 않기로 했지만 그렇지 않은 모습
- 하지만 두 번째 코드는 fibo_bottom_up2(10)을 계산했다면 $\operatorname{dp}[0]$ ~ $\operatorname{dp}[10]$까지 값이 채워져 있기에 fibo_bottom_up2(9)를 계산하지 않고 $\operatorname{dp}[9]$를 통해 fibo(9)를 계산할 수 있음
- 하지만 공간복잡도(메모리 사용) 측면으로 보면 첫 번째 코드가 두 번째 코드보다 메모리를 덜 잡아먹는다 (두 번째 코드는 충분히 큰 배열이 필요함)
- 결론: 상황에 맞게 사용하자