개념
DP는 "Dynamic Programming"의 약자로, 동적 계획법이라고도 불리는 알고리즘 설계 기법입니다. DP는 큰 문제를 작은 부분 문제로 분할하여 해결하고, 중복되는 부분 문제들을 한 번만 계산하여 효율적으로 해결하는 기법입니다. DP는 최적 부분 구조와 중복 부분 문제의 성질을 가진 문제에 적용됩니다.
작동 방식
-
큰 문제를 작은 하위 문제로 분할: DP는 큰 문제를 작은 하위 문제들로 분할하여 해결합니다. 이를 위해 전체 문제를 하위 문제들로 쪼개고, 하위 문제들 간에 어떤 관계가 있는지 파악합니다.
-
하위 문제의 최적 해 구하기: 각 하위 문제에 대해 최적의 해를 구합니다. 이때, 이미 해결된 작은 하위 문제의 해결 방법을 활용하여 더 큰 하위 문제의 해를 구할 수 있습니다. 이렇게 작은 하위 문제들을 해결하면서 점진적으로 더 큰 문제의 해를 구해나갑니다.
-
중복되는 부분 문제 제거: DP의 핵심은 중복되는 부분 문제를 효율적으로 제거하는 것입니다. 이미 해결한 하위 문제의 해답을 저장하고 재사용함으로써 중복 계산을 방지합니다. 이를 위해 주로 메모이제이션(Memoization)이나 테이블을 활용합니다.
-
최종 결과 도출: 모든 작은 하위 문제들을 해결하여 최종적인 큰 문제의 해를 도출합니다. 일반적으로 DP는 작은 하위 문제들을 해결하는 순서에 따라 상향식(bottom-up)으로 진행됩니다.
DP는 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)를 가지는 문제에 대해 효과적으로 적용될 수 있습니다. 예를 들어, 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS), 최단 경로 문제 등 다양한 문제에 DP를 적용할 수 있습니다. DP는 작은 문제의 해결을 통해 전체 문제의 최적해를 찾아내는 강력한 알고리즘 기법으로 활용됩니다.
특징
-
중복 부분 문제(Overlapping Subproblems): DP는 작은 부분 문제들을 해결하는 과정에서 중복되는 부분 문제들이 발생합니다. 이는 작은 문제들을 반복적으로 해결하며 이전에 계산한 결과를 저장하고 재사용함으로써 중복 계산을 피할 수 있습니다. 중복 부분 문제의 발생 여부는 DP를 적용할 수 있는 중요한 조건입니다.
-
최적 부분 구조(Optimal Substructure): 큰 문제의 최적해는 작은 부분 문제들의 최적해로부터 구성될 수 있습니다. DP는 큰 문제를 작은 부분 문제로 분할하여 해결하고, 작은 부분 문제들의 최적해를 활용하여 전체 문제의 최적해를 구할 수 있습니다. 이를 위해서는 작은 문제들의 최적해가 큰 문제의 최적해로 이어지는지를 보장하는 최적 부분 구조가 존재해야 합니다.
-
부분 문제의 독립성: DP는 작은 부분 문제들을 독립적으로 해결할 수 있어야 합니다. 즉, 한 부분 문제의 해결에 다른 부분 문제의 결과가 영향을 주지 않아야 합니다. 이는 각 부분 문제들을 독립적으로 해결할 수 있는 경우에 DP를 적용할 수 있는 중요한 조건입니다.
-
작은 문제에서 최적해 추론: DP는 작은 부분 문제들의 최적해를 활용하여 큰 문제의 최적해를 추론하는 방식으로 동작합니다. 작은 문제에서 최적해를 구하고, 이를 이용해 점진적으로 큰 문제의 최적해를 도출합니다. 작은 문제에서 최적해를 구하는 단계는 재귀적이거나 반복적인 접근 방식으로 이루어집니다.
-
메모이제이션(Memoization): DP는 이전에 계산한 결과를 저장하고 재사용하는 메모리 기법과 함께 사용될 수 있습니다. 이를 통해 중복 계산을 피하고 실행 시간을 줄일 수 있습니다. 계산한 결과를 저장하는 배열이나 테이블을 사용하여 메모리를 관리합니다.
구현 방법
-
상향식(Top-Down) 접근 방법 (메모이제이션 방식):
재귀 함수나 반복문을 사용하여 작은 부분 문제들을 해결하고, 중복되는 계산을 피하기 위해 이전에 계산한 결과를 저장합니다.
보통 재귀 함수를 이용하여 큰 문제를 작은 부분 문제들로 분할하고, 이전에 계산한 결과를 저장하기 위한 배열 또는 테이블을 사용합니다.
부분 문제들을 해결하면서 필요한 값들을 메모이제이션하여 중복 계산을 피하고 효율적으로 문제를 해결합니다.
재귀 함수를 호출하면서 이전에 계산한 결과가 이미 존재하는지를 확인하고, 존재한다면 해당 결과를 반환하고 계산을 중단합니다. -
하향식(Bottom-Up) 접근 방법 (테이블 방식):
작은 부분 문제들부터 시작하여 점진적으로 큰 문제들을 해결하는 방식입니다.
작은 부분 문제들을 해결하면서 필요한 값을 저장하기 위한 배열 또는 테이블을 사용합니다.
작은 문제들의 최적해를 계산하고, 이를 활용하여 점진적으로 큰 문제들의 최적해를 구합니다.
작은 문제부터 차례대로 계산하며 중복 계산을 피하고 최종적으로 원하는 큰 문제의 최적해를 구합니다.
이러한 방법을 활용하여 DP를 구현하면 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다. 구현 시에는 문제의 성질과 요구사항에 따라 적절한 방식을 선택하여 사용합니다.
