14. 동적 계획법(Dynamic Programming)
+ 원리
+ 현재 문제의 환경을 알고 있음
+ 문제를 작은 문제들로 분할
+ 작은 문제를 다 풀면 큰 문제를 해결 가능
+ 부분 문제 풀이의 결과를 다음 부분(중복) 문제를 풀 때 사용
+ 특징
+ 최적 하위구조 : Optimal Substructure\
+ 최적의 세부 구조가 있다
+ 답을 구하기 위해 했던 계산을 반복해야하는 문제의 구조
+ 중복 하위문제 : Overlapping Problems
+ 작은 문제들의 해답이 겹침
+ 분할정복 VS 동적 계획법
+ 분할 정복
+ 문제 풀이의 결과가 독립적
+ 동적 계획법
+ 문제들의 풀이 결과가 겹친다
+ 결과값을 메모리에 저장 -> 캐싱
def fib_naive(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_naive(n-1) + fib_naive(n-2)
print(fib_naive(10))
%%time
print(fib_naive(35))
# print(fib_naive(10000))
14-1. 메모이제이션(Memoization)
+ 하향식 접근법 : Top-Down
+ 하위 문제의 정답을 확인하며 상위 문제의 해답을 구함
+ 중복되는 결과값이 나오는 동일한 계산을 죽이기 위해 결과를 임시 저장
+ 캐싱 : Caching
fib_array = [0, 1]
def fib_recur_dp(n):
if n <= len(fib_array) - 1:
return fib_array[n]
else:
fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
fib_array.append(fib)
return fib
print(fib_recur_dp(10))
%%time
print(fib_recur_dp(35))
# print(fib_recur_dp(10000))
14-2. 태뷸페이션(Tabulation)
+ 상향식 접근법 : Bottom-up
+ 하위 문제부터 살펴보고 상위 문제로 이동
+ 캐싱
+ 메모이제이션 VS 태뷸레이션
+ 메모이제이션 : Lazy-Evaluation
+ 태뷸레이션 : Eager-Evaluation
def fib_dp(n):
fib_array = [0,1]
for i in range(2, n+1):
num = fib_array[i-1] + fib_array[i-2]
fib_array.append(num)
return fib_array[n]
print(fib_dp(10))
%%time
print(fib_dp(35))
print(fib_dp(10000))
