[Algorithm] 다이나믹 프로그래밍 Dynamic Programming

다이나믹 프로그래밍 (Dynamic Programming, DP)란? 다이나믹 프로그래밍 (이하 DP)란 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 분할정복과 비슷하다고 생각할 수 있지만 분할정복은 작은 문제가 중복이 일어나지 않고, DP는 반복(작은 문제의 결과가 같다)된다. 그래서 DP에서는 작은 문제들이 반복되는 것을 이용해 문제를 풀어나간다. 포인트는 모든 작은 문제들은 중복을 제거하고 한번만 풀어야 한다는 점이다. 따라서 정답을 구한 작은 문제들을 어딘가에 메모(Memoization)해둔다. 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 많이 언급하는 피보나치 수열 문제를 예시로 들어보자. ..