동적 계획법
동적 계획법 (Dynamic Programming)
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 부분 문제(Subproblem)로 나누어 풀고, 그 부분 문제들의 해를 저장해두었다가 재사용함으로써 전체 문제의 해를 구하는 알고리즘 기법입니다. 단순 재귀 방식에서 발생하는 중복 계산을 피하여 성능을 최적화하는 데 중점을 둡니다.
🎯 DP를 적용하기 위한 조건
어떤 문제를 DP로 해결하기 위해서는 아래의 두 가지 조건을 모두 만족해야 합니다.
- 최적 부분 구조 (Optimal Substructure)
> * '정의': 문제의 최적 해결책이, 그 문제를 구성하는 작은 부분 문제들의 최적 해결책으로부터 구해질 수 있는 구조를 의미합니다. > * '예시': 피보나치 수열에서 `fib(n)`은 `fib(n-1)`과 `fib(n-2)`의 합으로 구성됩니다.
- 중복되는 부분 문제 (Overlapping Subproblems)
> * '정의': 하나의 문제를 여러 개의 작은 부분 문제로 나누었을 때, 동일한 부분 문제가 반복적으로 나타나는 구조를 의미합니다. > * '예시': `fib(5)`를 구하기 위해 `fib(3)`이 두 번 계산되는 것처럼, 재귀적으로 문제를 풀 때 같은 연산이 여러 번 반복됩니다. DP는 이 중복 계산을 피하기 위해 한 번 계산한 결과를 저장합니다.
🛠️ DP의 구현 방식
- 메모이제이션 (Memoization) - Top-down 방식
> * '방식': 재귀 호출을 기반으로 문제를 해결하되, 한 번 계산한 부분 문제의 결과를 배열이나 해시 테이블(캐시)에 저장해두고, 다음에 같은 문제가 나타나면 저장된 결과를 그대로 사용하는 방식입니다. > * '특징': 실제 필요한 부분 문제만 계산하게 되며, 재귀를 사용하므로 코드가 직관적일 수 있습니다.
- 타뷸레이션 (Tabulation) - Bottom-up 방식
> * '방식': 반복문을 사용하여 가장 작은 단위의 부분 문제부터 차례대로 해를 구해나가, 최종적으로 원래 문제의 해를 구하는 방식입니다. 결과는 보통 DP 테이블(배열)에 저장됩니다. > * '특징': 모든 부분 문제를 순차적으로 계산하며, 재귀를 사용하지 않아 스택 오버플로우의 위험이 없습니다. 일반적으로 메모이제이션보다 성능이 더 좋습니다.
💡 개발자 핵심 Point
- 동적 계획법은 문제를 정의하고 점화식을 세우는 것이 가장 중요하고 어려운 부분입니다.
1. DP로 풀 수 있는 문제인지 확인 (위의 두 가지 조건). 2. '상태(State) 정의': DP 테이블의 각 인덱스가 무엇을 의미하는지 정의합니다. 3. '점화식(Recurrence Relation) 정의': 상태들 간의 관계를 식으로 표현합니다. 4. '초기값(Base Case) 정의': 가장 작은 단위의 문제에 대한 해를 정의합니다.
- 그리디 알고리즘(Greedy Algorithm)과의 차이
> * 그리디: 매 순간 '지역적으로 최적'인 선택을 합니다. 이 선택이 '전역적으로도 최적'임이 보장될 때만 사용 가능합니다. > * DP: 모든 가능한 선택지를 고려하여, 부분 문제들의 최적해를 바탕으로 '전역 최적해'를 구합니다.
- 대표적인 DP 문제 : 피보나치 수열, 최장 증가 부분 수열 (LIS), 배낭 문제 (Knapsack Problem), 편집 거리 (Edit Distance) 등이 있습니다.
