[Do it! 알고리즘 코딩테스트 with Python] 동적 계획법

동적 계획법의 원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.

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

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

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

 

동적 계획법의 대표 문제

D[n] = D[n-1] + D[n-2]

 

Tip!

1. 아 여기서 여기.. 여기서 여기 ( x )

6번째를 찾을 거야! 1, 2, 3, 4, 5번째 숫자가 이렇게 있네? 이들의 관계가 어떻길래 저렇게 나온거지?

→ 그렇게 하고 일반화하기!!

 

2. 시간 복잡도 주의