Dynamic Programming (동적 계획법)

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

 

원리

1) 큰 문제를 작은 문제로 나눈다.

2) 작은 문제들이 반복되어 나타나고 사용되며, 작은 문제들의 결괏값은 항상 같아야 한다.

3) 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다 → ★memoization★

4) 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

 

 

코드 예시

def fibo_dp(n):
    cache = [0 for idx in range(n+1)] # memoization
    cache[0] = 0
    cache[1] = 1
    
    for idx in range(2,n+1):
        cache[idx] = cache[idx-1] + cache[idx-2]
    return cache[n]

 

 

푸는 과정

1) 테이블 정의하기

2) 점화식 찾기

3) 초기값 정하기

 

 

 

출처 : 바킹독, 잔재미코딩, Do it! 알고리즘 코딩 테스트(Python)