동적 프로그래밍 (Dynamic Programming)
동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하는 최적화 기법입니다. 동적 프로그래밍은 주로 재귀적으로 정의할 수 있는 문제에서 사용되며, 동일한 하위 문제가 여러 번 반복될 때, 이를 저장(memoization)하여 불필요한 계산을 줄여 성능을 개선합니다. 대표적인 동적 프로그래밍 문제로는 피보나치 수열, 배낭 문제, 최장 공통 부분 수열 등이 있습니다.
1. 피보나치 수열 (Fibonacci Sequence)
피보나치 수열은 첫 두 항이 0과 1로 시작하고, 이후의 항은 바로 이전 두 항의 합으로 정의되는 수열입니다. 재귀적으로 정의할 수 있지만, 동일한 계산이 반복되기 때문에 동적 프로그래밍을 사용하면 성능을 크게 개선할 수 있습니다.
피보나치 수열 정의
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)
피보나치 수열 동적 프로그래밍 예제 코드
// 피보나치 수열 (동적 프로그래밍) - JavaScript
function fibonacci(n) {
let dp = [0, 1]; // F(0) = 0, F(1) = 1
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibonacci(10)); // 55
동적 프로그래밍을 사용한 피보나치 수열의 시간 복잡도는 O(n)으로, 재귀적 방식에 비해 훨씬 효율적입니다. 이는 매번 동일한 값을 중복해서 계산하지 않고, 한 번 계산된 값을 저장해둔 덕분입니다.
2. 배낭 문제 (Knapsack Problem)
배낭 문제는 주어진 아이템들 중 일부를 선택하여 배낭의 최대 용량을 초과하지 않으면서 최대 가치를 얻는 문제입니다. 이 문제는 주로 "0/1 배낭 문제"로 알려져 있으며, 아이템을 선택하거나 선택하지 않는 두 가지 선택을 제공합니다. 동적 프로그래밍을 사용하여 최적의 해를 구할 수 있습니다.
문제 정의
주어진 아이템 각각의 무게와 가치가 있고, 배낭의 최대 무게를 초과하지 않으면서 가치를 최대화하는 것이 목표입니다.
W = 배낭의 최대 무게
n = 아이템의 개수
w[i] = i번째 아이템의 무게
v[i] = i번째 아이템의 가치
K(n, W) = {
K(n-1, W) (아이템 n을 포함하지 않음),
max(v[n-1] + K(n-1, W-w[n-1]), K(n-1, W)) (아이템 n을 포함함)
}
배낭 문제 동적 프로그래밍 예제 코드
// 0/1 배낭 문제 (동적 프로그래밍) - JavaScript
function knapsack(values, weights, capacity) {
let n = values.length;
let dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
let values = [60, 100, 120];
let weights = [10, 20, 30];
let capacity = 50;
console.log(knapsack(values, weights, capacity)); // 220
배낭 문제에서 동적 프로그래밍을 사용하면 시간 복잡도는 O(nW)로, 여기서 n은 아이템의 수, W는 배낭의 최대 무게입니다. 이렇게 하여 최적의 선택을 계산할 수 있습니다.
3. 최장 공통 부분 수열 (Longest Common Subsequence)
최장 공통 부분 수열(LCS)은 두 문자열에서 공통으로 나타나는 부분 수열 중 가장 긴 수열을 찾는 문제입니다. 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있습니다.
문제 정의
두 문자열 X와 Y가 있을 때, X와 Y의 가장 긴 공통 부분 수열을 찾는 것이 목표입니다. 예를 들어, X = "AGGTAB", Y = "GXTXAYB"일 때, 최장 공통 부분 수열은 "GTAB"이며, 길이는 4입니다.
LCS(X, Y, m, n) = {
0, if m == 0 or n == 0
LCS(X, Y, m-1, n-1) + 1, if X[m-1] == Y[n-1]
max(LCS(X, Y, m-1, n), LCS(X, Y, m, n-1)), if X[m-1] != Y[n-1]
}
최장 공통 부분 수열 동적 프로그래밍 예제 코드
// 최장 공통 부분 수열 (동적 프로그래밍) - JavaScript
function lcs(X, Y) {
let m = X.length;
let n = Y.length;
let dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (X[i - 1] === Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
let X = "AGGTAB";
let Y = "GXTXAYB";
console.log(lcs(X, Y)); // 4
최장 공통 부분 수열의 시간 복잡도는 O(mn)으로, 두 문자열의 길이에 비례하여 성능이 결정됩니다. 동적 프로그래밍을 사용함으로써 모든 하위 문제를 한 번만 계산하여 성능을 최적화할 수 있습니다.
결론
동적 프로그래밍은 복잡한 문제를 효율적으로 해결하는 기법입니다. 피보나치 수열, 배낭 문제, 최장 공통 부분 수열과 같은 문제에서, 동일한 하위 문제를 여러 번 해결하는 대신, 동적 프로그래밍은 이를 저장하여 중복 계산을 피하고 성능을 개선합니다. 이러한 기법은 최적화 문제나 재귀적으로 정의되는 문제를 해결하는 데 매우 유용합니다.