다이나믹 프로그래밍

정의

문제를 푸는 알고리즘 기법중 하나로 커다랗고 복잡한 문제를 작고 심플한 문제들로 나누어서 푸는 방법을 뜻합니다.

예제

$2^1+2^2+2^3+2^4+2^5$
위 문제를 푼다고 가정했을때,

$2^1=2=2$

$2^2=22=2^12$

$2^3=222=2^2*2$

$2^4=2222=2^32$

$2^5=22222=2^4*2$

위와 같이 특정 계산($2^1,2^2,2^3,2^4$)은 쓸대없이 반복됨을 알수 있습니다. $2^4$를 계산할때 이미 $2^3$을 알고 있다면, 굳이 $2^3$을 다시 계산할 필요는 없습니다. 앞에 계산된 가격에 2만 더함으로서 추가적인 계산을 하지않고 조금더 효율적인 알고리즘을 만드는것이 가능합니다.