DP(Dynamic Programming, 동적 계획법)

Dynamic Programming(동적 계획법)은 1950년대에 리차드 벨만(Richard Bellman)이 알고리즘 최적화를 위해 제안한 전략입니다. 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결합니다. 분할정복 알고리즘은 문제를 독립적인 부분 문제로 분할하고, 부분 문제들을 재귀적으로 해결한 후, 그 결과들을 결합하여 원래의 문제를 해결하는데 반에 DP는 부분 문제들이 서로 독립적이지 않을 때, 즉, 부분 문제들이 다시 자신의 부분 문제를 공유할 때 적용할 수 있습니다. 분할정복 알고리즘은 공유되는 부분 문제들을 반복적으로 해결 함으로써 필요이상의 더 많은 일을 하게 됩니다. 이러한 분할정복 알고리즘의 문제점을 DP는 모든 부분 문제들을 단 한번만 풀고, 그 해를 테이블에 저장함으로써 부분 문제를 반복해야할 때마다 다시 계산하는 일을 피할 수 있습니다.

 

▶ DP(동적 프로그래밍) 알고리즘의 개발은 4단계

    1. 최적해의 구조를 찾는다.

    2. 최적해의 값을 재귀적으로 정의한다.

    3. 최적해의 값을 하향식(Top-Down), 상향식(Bottom-Up) 방법으로 계산한다.

    4. 계산된 정보들로부터 최적해를 구한다.

 

▶ 주요 개념

    ∙ 부분 문제 : 동적 계획법에서는 큰 문제를 작은 부분 문제들로 나누어 해결합니다.

                 각 부분 문제는 독립적으로 해결될 수 있으며, 그 결과는 저장되어 재사용됩니다.

    ∙ 점화식 : 부분 문제들 간의 관계를 나타내는 식입니다. 이 식은 이전 단계의 해를 이용하여

                 현재 단계의 해를 구하는 데 사용됩니다.

    ∙ 메모이제이션 : 이미 계산한 부분 문제의 해를 저장하고, 같은 문제가 다시 발생할 때 저장된 해를

                재사용하는 기법입니다. 이를 통해 중복 계산을 방지하고 시간 복잡도를 줄일 수 있습니다.

    ∙ 최적 해 : 동적 계획법의 목표는 주어진 문제의 최적 해를 찾는 것입니다.

                 이는 모든 가능한 해 중에서 가장 좋은 해를 의미합니다.

 

▶ 적용 분야

    1. 피보나치 수열

    2. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

    3. 최소 편집 거리 (Edit Distance)

    4. 배낭 문제 (Knapsack Problem)

    5. 정수 삼각형 문제

    6. LCS (Longest Common Subsequence, 최장 공통 부분 수열)

    7. Matrix Chain Multiplication

    8. Coin Change Problem (코인 교환 문제)

    9. Coin Game (코인 게임)

    10. Counting Subsets (부분 집합 세기)

    11. Rod Cutting Problem (막대기 자르기 문제)

    12. Job Scheduling Problem (작업 스케줄링 문제)

    13. Edit Distance with Deletion and Insertion(삭제 및 삽입을 포함한 편집 거리)

    14. 게임 이론 : Nim 게임, Tic-Tac-Toe 게임 등.

    15. 그래프 탐색 알고리즘

    16. 정렬 알고리즘

 

▶ 시간 복잡도

동적 계획법의 시간 복잡도는 문제의 크기와 메모이제이션의 사용 여부에 따라 다릅니다. 일반적으로, 메모이제이션을 사용하지 않으면 O(2^n) 또는 O(n!)과 같은 매우 높은 시간 복잡도를 가질 수 있습니다. 하지만, 메모이제이션을 사용하면 O(nW) 또는 O(n^2)과 같은 더 낮은 시간 복잡도를 가질 수 있습니다. 여기서 W는 부분 문제의 최대 개수입니다.

 

▶ 장점

    ∙ 효율성 : 메모이제이션을 사용하면 중복 계산을 방지하여 효율적으로 문제를 해결할 수 있습니다.

    ∙ 일반성 : 동적 계획법은 다양한 문제에 적용할 수 있는 일반적인 방법입니다.

    ∙ 최적 해 : 동적 계획법은 최적 해를 보장합니다.

 

▶ 단점

    ∙ 복잡성 : 동적 계획법은 구현이 복잡하고 어려울 수 있습니다.

                    특히, 점화식을 찾는 것이 어렵습니다.

    ∙ 메모리 사용량 : 메모이제이션을 사용하면 메모리 사용량이 증가할 수 있습니다.

    ∙ 제한성 : 모든 문제에 동적 계획법을 적용할 수 있는 것은 아닙니다.

                   일부 문제는 동적 계획법보다 더 효율적인 다른 방법이 있을 수 있습니다.

 

 

출처]

INTODUCTION TO ALOGRITHMS : 동적 프로그래밍(p343)

프로그래머가 알아야할 알고리즘 40 : 동적 계획법 이해하기(p107)

CLOVA X(Naver), Gemini(Google)

    Pormpt : Dynamic Programming에 대하여 자세히 설명해 주세요.

 

 

참고 문제]

C언어 192제] 평범한 배낭

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 여름