Dynamic Programming

휜·2025년 9월 14일

javscript 알고리즘

Algorithm

목록 보기

5/7

Dynamic Programming

개요

큰 문제를 작은 문제들로 나누어 해결하는 기법
동적 계획법이라고도 한다. 약어로는 DP

중복되는 부분 문제들이 존재할 때, 한 번 계산한 결과를 저장해두고 나중에 같은 문제가 나오면 저장된 값을 재사용한다

💡 즉, 같은 계산을 여러 번 해야할 때, 첫 번째로 계산한 결과를 메모해두고 다시 사용하는 것과 같음. 💡

예시

1. 피보나치 수열

피보나치 수열: 1, 1, 2, 3, 5, 8, 13, 21...
(앞의 두 수를 더하면 다음 수가 됨)

// ❌ 비효율적인 방법 (같은 계산을 반복)
function fibonacciBadCase(n) {
    if (n <= 1) return n;
    return fibonacciBadCase(n-1) + fibonacciBadCase(n-2);
}

// ✅ Dynamic Programming 방법 (메모이제이션)
function fibonacciDP(n, memo = {}) {
    if (n in memo) return memo[n]; // 이미 계산했으면 바로 반환
    if (n <= 1) return n;
    
    memo[n] = fibonacciDP(n-1, memo) + fibonacciDP(n-2, memo);
    return memo[n];
}

console.log(fibonacciDP(10)); // 55

2. 계단 오르기 문제

계단을 오를 때 한 번에 1칸 또는 2칸씩 올라갈 수 있다면, n칸 계단을 오르는 방법의 수는?

function climbStairs(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 2) return n;
    
    memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
    return memo[n];
}

console.log(climbStairs(5)); // 8가지 방법
// 1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2

3. 최소 동전 개수 문제

특정 금액을 만들기 위해 필요한 최소 동전 개수 구하기

function minCoins(amount, coins, memo = {}) {
    if (amount in memo) return memo[amount];
    if (amount === 0) return 0;
    if (amount < 0) return Infinity;
    
    let min = Infinity;
    for (let coin of coins) {
        const result = minCoins(amount - coin, coins, memo);
        if (result !== Infinity) {
            min = Math.min(min, result + 1);
        }
    }
    
    memo[amount] = min;
    return min;
}

console.log(minCoins(11, [1, 4, 5])); // 3개 (5+5+1)

4. 최대 부분 배열 합 (Kadane's Algorithm)

배열에서 연속된 부분 배열의 최대 합 구하기

function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // 현재까지의 합 vs 새로 시작하는 것 중 더 큰 값
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 (4+-1+2+1)

5. 배낭 문제

용량이 제한된 배낭에 가치가 최대가 되도록 물건 넣기

function knapsack(capacity, weights, values, n, memo = {}) {
    const key = `${capacity}-${n}`;
    if (key in memo) return memo[key];
    
    // 기저 조건
    if (n === 0 || capacity === 0) return 0;
    
    // 현재 물건이 배낭 용량보다 크면 포함할 수 없음
    if (weights[n-1] > capacity) {
        memo[key] = knapsack(capacity, weights, values, n-1, memo);
        return memo[key];
    }
    
    // 현재 물건을 포함하는 경우와 포함하지 않는 경우 중 최대값
    const include = values[n-1] + knapsack(capacity - weights[n-1], weights, values, n-1, memo);
    const exclude = knapsack(capacity, weights, values, n-1, memo);
    
    memo[key] = Math.max(include, exclude);
    return memo[key];
}

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
console.log(knapsack(7, weights, values, 4)); // 9 (무게3+4, 가치4+5)