Dynamic Programing

Dynamic Programing은 목표한 문제를 풀기 위해 위상적으로 연결된 부분 문제들로 나누어 푸는 방법이다.

 

예를 들어 "D"라는 해결하기 까다로운 문제가 있을 때, 먼저 "A"라는 답을 자명히 낼 수 있는 부분문제로부터 시작한다. 이 자명해로부터 "B"를 해결하고, 그로부터 "C"를 해결하는 연속적인 과정을 거쳐, 마지막으로 문제 "D"를 해결하는 것이 DP이다. 이때, A로부터 B를 도출하고, B로부터 C를 도출하고, C로부터 D를 도출하는 이 부분문제간의 간선, 즉 규칙성은 문제가 무엇이냐에 따라 다르며, 이를 점화식으로써 명확히 하는 것이 DP의 핵심이다.

 

점화식을 구한 뒤에는, 문제가 단순하고 변수가 적을 경우 (피보나치, 하노이 등) 점화식으로부터 수학적으로 일반항을 직접 구해 바로 본 문제의 해답을 구할 수도 있겠지만, 일반적으로는 그렇지 못하기 때문에 본 문제에 도달할 때까지 연속적인 문제 해결과정을 거치게 된다. 이때, 이 연속적인 과정에서 중복되는 연산을 생략하기 위해 메모이제이션을 이용한다.

 

메모이제이션에 필요한 메모리 테이블의 크기는 점화식의 변수와 그 range에 따라 결정된다. 즉, 치역의 크기와 같다. 예를 들어 일변수 점화식에서 0차항을 아는데 풀어야 할 문제가 n차항에 해당하는 경우 n의 메모리가 필요하며, 이변수 점화식에서 (m, n)항을 구해야 할 경우 메모리는 m*n이 필요하다.

 

원론적으로는 그렇지만, 이를 더 효율적으로 처리하기 위한 각종 DP 최적화 trick들이 존재하며 각 트릭은 점화식이 특정 컨디션을 만족할 때 적용이 가능하다. 대표적으로 Convex Hull Trick (볼록 껍질을 이용한 최적화), Divide and Conquer Optimization (분할 정복을 이용한 최적화) 등이 있는데, 각각의 트릭들이 모두 수학적 깊이를 필요로 해서 따로 공부하진 않고 이런게 있다 정도로만 염두에 두고 있다. 존재는 알고 있으니 필요한 때가 오면 배워서 쓸 거라 믿는다.