Always Be Wise

동적 프로그래밍(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 방법을 의미한다. 여러 개의 문제로 나누어 해결한다는 점에서 분할 정복(Divide and Conquer)과 유사해 보이지만, 동적 프로그래밍의 경우, 간단한 문제들이 반복적으로 일어난다는 점에서 차이가 있다. 즉, 동적 프로그래밍은 간단한 문제들을 한 번만 해결하고 그보다 복잡한 문제를 풀어나갈 때 똑같은 간단한 문제가 다시 나타나면 그 결과 값을 이용해해결하는 방법이다. 이때, 간단한 문제의 결과 값을 기억하여 반복 수행을 제거하는 과정을 메모이제이션(Memoization)이라고 한다. 동적 프로그래밍을 사용하려면 아래 두 가지 조건을 만족해야 한다. 1. 부분 문제 반복(Overlapp..