DP - 동적 계획법
다이나믹 프로그래밍 (Dynamic Programming, DP) 알고리즘은 응용 수학자 리차드 벨만이 고안한 알고리즘으로, 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해두었다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다.
알고리즘의 원리와 이름과는 큰 관계가 없어보이는데, 이런 이름이 붙게 된 이유는 당시 벨 연구소에 재직중이던 리차드 벨만이 자금 지원을 받기 위해 멋있어 보이는 이름을 택했기 때문이라고 한다. 적당히 ‘기억하며 풀기’ 알고리즘 정도로 생각하면 될 것 같다.
DP를 이용하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 문제, 즉 최적 부분 구조(Optimal Substructure)를 갖고 있는 문제를 풀이할 수 있다. 그리디 알고리즘과의 차이는 중복된 하위 문제들 (Overlapping Subproblems)의 결과를 저장해뒀다가 풀이해 나간다는 점이다. 여기서 중요한 점은 ‘중복된’ 문제들이란 점이며, 중복되지 않는 문제들은 DP로 풀지 않는다. 중복되지 않는 문제에는 대표적으로 병합 정렬과 퀵 정렬 등이 있으며, 이들은 모두 분할 정복 알고리즘으로 분류한다.
최적 부분 구조란?
서울에서 부산까지 가는 최단 경로를 찾는 간단한 예를 들어보자. 그림에서 볼 수 있듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 대구에서 부산까지도 마찬가지로 3가지 경로가 있다. 서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km이다.
이 경로는 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다. 즉, 서울에서 부산까지 가는 최단 경로는 각각의 부분 문제의 해결 방법의 합이다.
이러한 구조를 최적 부분 구조라 하며, 이런 유형의 문제는 분할 정복으로 풀 수 있다. 또한, 다이나믹 프로그래밍 또는 그리디 알고리즘으로 접근해볼 수 있는 문제의 후보가 된다.
