동적 프로그래밍(Dynamic programming) - 하위의 작은 문제들을 풀고, 이를 이용해서 더 큰 문제를 풀어나가는 방법 - 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 - 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용 - 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용 그리디 알고리즘 비교 - 동적 프로그래밍은 가능한 모든 방법을 고려해야 한다는 단점 - 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리..
