오늘은 백준 1932번 문제를 풀어보며
동적 계획법에 대해 어떻게 접근해야 하는지 감을 잡았다.
동적 계획법에 대한 설명을 위키트리에서 발췌해 보자면
****동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
동적 계획법은 위에서 설명했듯이, 가능한 모든 방법을 고려해야 한다는 단점이 있다. 이러한 단점을 극복하기 위하여, 동적 계획법 대신 그리디 알고리즘이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증되었다.****
그 내용을 위와 같이 요약할 수 있다.
이것을 다시 내 식대로 해석하자면
동적 계획법은 "그리디알고리즘 + 백트랙킹 + 메모이제이션" 이라고 요약할 수 있다,
