다이나믹 프로그래밍하나의 큰 문제를 해결하기 위해서, 여러 개의 작은 문제로 나누어 해당 문제들을 푼 후, 이를 쌓아올려 주어진 큰 문제를 해결하도록 하는 알고리즘이다.이름의 유래?Dynamic에는 별 뜻이 없고, 리처드 벨만이 “Dynamic” 이라는 단어가 멋있어 보여서 붙였다고 한다. Programming은 최적화 연구에서 최적의 프로그램을 찾을 때 쓰는 단어라고 한다.이러한 다이나믹 프로그래밍(Dynamic Programming, DP)은 아래 두 가지 조건을 만족하는 문제에서 사용할 수 있다.Optimal Substructure(최적 부분 구조): 전체 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되어야 한다.Overlapping Subproblems(부분 문제 반복): 동..