[Algorithm] 동적 계획법(Dynamic Programming)

참조 :

https://developer-mac.tistory.com/77

[코딩테스트 대비] 동적 계획법 (DP) 정리

 

Dynamic Programming이란?

큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법이다.

 

DP 속성

Overlapping Subproblem(부분 문제가 겹친다.)
Optimal Substructure(최적 부분 구조)

 

Overlapping Subproblem

대표적인 예로 피보나치 수를 들 수 있다.
Fn = (Fn-1) + (Fn-2)

여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 (Fn-1)과 (Fn-2)를 작은 문제로 나눈다고 생각하면 된다.

 

Optimal Substructure

문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.
위의 예에서 작은 문제로 쪼갠 우측 항의 (Fn-1)과 (Fn-2)의 합으로 큰 문제인 Fn의 값을 구할 수 있다.