DP(Dynamic Programming) 동적 프로그래밍 이란?

DP(Dynamic Programming) 알고리즘은

 

최적화 문제를 해결하기 위한 알고리즘 디자인 기법 중 하나입니다.

이 알고리즘은 문제를 여러 하위 문제(subproblem)로 나누고,

각 하위 문제의 최적해를 저장하며 전체 문제의 최적해를 구하는 방식으로 동작합니다.

 

-> 중복되는 하위 문제들을 효율적으로 해결하여 전체 문제의 최적해를 구할 수 있습니다.

 

 

DP 알고리즘의 핵심 아이디어는?

"작은 문제의 최적해로부터 큰 문제의 최적해를 구할 수 있다"는 점입니다.

따라서 DP 알고리즘은 작은 하위 문제의 최적해를 계산하고 저장하며,

이를 이용하여 큰 문제의 최적해를 구하는 과정을 반복합니다.

 

 

DP 알고리즘의 구체적인 동작 방식

문제를 하위 문제로 나눕니다

-> 주어진 최적화 문제를 작은 하위 문제들로 분할합니다. 이때, 하위 문제는 중복되는 부분 문제들을 갖도록 선택합니다.

 

하위 문제의 최적해를 정의합니다

-> 각 하위 문제에 대해 최적해를 정의하고 문제의 조건에 맞게 수식으로 표현합니다.

이때, 최적해는 원래 문제의 최적해와 일치해야 합니다.

 

최적해의 값을 계산합니다

-> 작은 하위 문제부터 시작하여 최적해의 값을 계산합니다.

각 하위 문제의 최적해를 저장하고, 저장된 값을 이용하여 상위 문제의 최적해를 구합니다.

이 과정은 상향식(bottom-up)으로 진행됩니다.

 

최적해를 추적합니다(선택적)

-> 필요한 경우, 계산된 최적해를 추적하여 원래 문제의 최적해를 찾습니다.

이 단계는 선택사항이며, 모든 문제에 적용되지 않습니다.

 

 

DP 알고리즘은 많은 문제에 적용될 수 있음

예를 들면, 피보나치 수열, 최장 공통 부분 수열(Longest Common Subsequence), 최단 경로 문제 등이 있습니다.

이러한 문제들은 중복되는 하위 문제들을 갖고 있으며, DP 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.

 

 

마무리

DP 알고리즘은 최적화 문제에 적합한 알고리즘 디자인 기법으로,

중복되는 하위 문제들을 활용하여 문제의 최적해를 효율적으로 계산할 수 있습니다.

 

하지만 모든 문제에 적용 가능한 것은 아니며,

적용 가능한 문제에 대해서는 적절한 하위 문제 분할과 최적해 정의가 필요합니다.