다이나믹 프로그래밍(Dynamic Programming, DP)
다이나믹 프로그래밍은 문제를 여러 작은 하위 문제로 나누어 해결한 결과를 저장해두고, 이를 재사용하여 전체 문제를 해결하는 알고리즘 기법입니다. 주로 최적화 문제를 해결하는 데 많이 사용됩니다.
대표적인 DP 문제로는 피보나치 수열, 최단 경로 문제, 배낭 문제, 최장 증가 부분 수열 등이 있습니다.
DP의 사용 조건
DP가 효과적으로 적용되기 위해서는 두 가지 조건을 만족해야 합니다.
1. 중복되는 부분 문제 (Overlapping Subproblems)
- 문제를 풀 때 동일한 작은 하위 문제가 반복해서 등장하는 경우, 그 결과를 저장해 중복 계산을 피해야 합니다.
- 예를 들어, 피보나치 수열을 계산할 때,
F(5)를 계산하려면F(4)와F(3)이 필요하고,F(4)를 계산할 때F(3)과F(2)가 다시 필요합니다. 이때F(3)을 한 번 계산해 저장해두면, 다른 곳에서 다시 계산할 필요 없이 재사용할 수 있습니다.
2. 최적 부분 구조 (Optimal Substructure)
- 전체 문제의 최적 해답을 구할 때, 하위 문제들의 최적 해답을 사용하여 풀 수 있어야 합니다.
- 예를 들어, 전체 경로에서 최적 경로를 구할 때, 하위 문제인 a에서 x까지의 경로와 x에서 b까지의 경로의 최적 값을 사용하면 전체 경로의 최적 값을 구할 수 있습니다.
DP 문제 해결 방식
DP 문제는 두 가지 방식으로 해결할 수 있습니다. 바텀업 방식과 탑다운 방식입니다.
1. 바텀업 방식(Bottom-Up) : 반복문 사용
작은 문제부터 차례대로 답을 구한 뒤, 그 답을 사용해 더 큰 문제를 해결하는 방식입니다. 반복문을 통해 문제를 해결하고, 결과를 배열 등에 저장해 나갑니다.
바텀업 방식은 메모리 효율이 좋고 스택 오버플로우 위험이 적습니다. 반복문을 사용해 일정한 크기의 배열만 사용하기 때문입니다.
function fib(n) {
const dp = [0, 1]; // 0과 1에 대한 기본값 저장
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}2. 탑다운 방식(Top-Down) : 재귀 + 메모이제이션 사용
큰 문제에서 작은 문제로 쪼개며 재귀적으로 푸는 방식입니다. 이때 메모이제이션을 통해 하위 문제의 결과를 저장해 중복 계산을 방지합니다.
탑다운 방식은 코드가 직관적이며 재귀적인 문제 해결에 적합하지만, 큰 입력에서는 스택 오버플로우의 위험이 있습니다.
const dp = [];
function fib(n) {
if(n <= 1) return n;
if(dp[n] !== undefined) return dp[n]; // 이미 계산한 값이면 저장된 값 사용
dp[n] = fib(n - 1) + fib(n - 2);
return dp[n]
}
console.log(fib(10));DP 문제 해결 팁
1. 작은 하위 문제로 나누기
먼저 문제를 어떻게 하위 문제로 나눌 수 있을지 생각합니다.
2. 상태 정의
각 하위 문제의 상태를 정의하고, 그 상태를 저장할 배열(혹은 변수)을 만듭니다.
3. 점화식 설정
현재 상태를 이전 상태로부터 어떻게 계산할지, 즉 문제 간의 관계를 수식으로 표현합니다.
4. 기저 조건 설정
가장 작은 문제의 값을 정의합니다. 예를 들어, 피보나치 수열에서는 F(0)=0 와 F(1)=1 의 값을 기본값으로 설정합니다.
해당 방법을 사용하여 푼 예시 문제는 [백준] 1로 만들기에서 확인할 수 있습니다.
