https://coding-all.tistory.com/2
간결
https://new93helloworld.tistory.com/220?category=691027
자세히
https://blog.naver.com/indiaesther/222556551906
상향식
하향식
동적계획법(Dynamic Programming)
동적계획법을 사용하는 문제 : 각 단계에 있는 부분의 답을 기반으로 전체 문제의 답을 구할때.
문제가 최적 부분 구조 를 충족할 때 : 최적 부분 구조란 전체 문제의 최적해가 부분문제의 최적해로부터 만들어지는 구조.
어떤 문제를 5개로 쪼갤 수 있을때, 그 5개를 모두 얻어야 이문제를 해결할 수 있다면 최적부분구조를 충족
Bottom-Up 구조 : 큰 수부터 작은 수를 구하는게 아닌 -> 작은 수부터 큰수를 구하며 해결
Top-Down 구조
문제를 해결할 때 큰 문제에서 , 작은 문제로 내려가는 구조 ex) fibonacci 문제를 재귀로 구현한 문제
상향식 구조
Bottom - Up 구조
문제를 해결할 때, 작은 문제에서, 큰 문제로 올라가는 구조
하향식 구조
중복 연산을 방지하는 방법
- Memoization
동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모이제이션(Memoization)이라고 한다. (하향식 풀이)
#피보나치 수열
def fib(n):
if n==0 or n == 1 :
return 1
else :
res = fib(n-1) + fib(n-2)
memo[n] = res # 메모이제이션
return res
2. Tabulation
Memoization 방식과 다르게 타뷸레이션(Tabulation)은 문제 풀이가 아래에서 위로 진행되는 것을 말한다. (상향식)
#피보나치 수열
def fib(n):
fiblist = [ 1, 1 ]
for i in range(2, n+1):
fiblist.append(fiblist[i-2] + fiblist[i-1]
return fiblist[-1] # 마지막 값 반환
출처동적 계획법(Dynamic Programming)|작성자 혜영밍
*구현 방법
1. Bottom-up/Tabulation 방식- 반복문 사용
풀이가 아래에서 위로 진행, 즉 작은 수부터 큰 수까지 ↗
(catche에 메모하는 방식으로 정리)
2. Top-down/ Memoriziation방식-재귀 사용
풀이가 위에서 아래로 진행, 즉 큰 수부터 작은수까짐 ↘
(Table 방식으로 정리)
