동적 계획법(Dynamic Programming)

동적 계획법은 정말 가장 많이 대회에서 출제되는 문제 유형임과 동시에 반드시 알아야만 하는 내용이기도 하다. 명확하게 '이것이 동적 계획법 문제다' 라고 분류하기 보다는 앞선 브루트 포스나 그리디 알고리즘과 같이 문제를 풀어나가는 하나의 방법으로 접근하는 것이 올바르다고 생각한다. 동적 계획법 역시 큰 문제를 작은 문제로 나누는 것에서 출발한다. 지금까지의 내용을 정리하면 아래와 같다. 브루트 포스(Brute Force): 작은 문제 하나하나 다 살펴볼거야! 탐욕법(Greedy): 작은 문제마다 답을 선택해 버릴거야! 그렇다면 동적 계획법의 메커니즘은 어떤 것일까? 다른 작은 문제에서 만들어 놓은 값을 다시 쓸거야! 즉, 작은 문제들로 분류하여 연산을 하는 과정에서 같은 연산을 반복적으로 수행해야 한다면..

원문링크 : 동적 계획법(Dynamic Programming)