17. 동적 프로그래밍 (Dynamic Programming) Codility Lesson 한국어 정리본 (JavaScript ver.)

동적 프로그래밍(Dynamic Programming)이란?

동적 프로그래밍(DP)은 작은 문제들의 해를 활용하여 더 큰 문제의 해를 구하는 알고리즘 기법 이다. 일반적으로 문제를 여러 작은 부분 문제로 나누고, 중복 계산을 줄이기 위해 결과를 저장(memoization) 하는 방식으로 사용된다.

동적 프로그래밍이 효과적인 경우:

• 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 부분 문제의 최적해로 구성될 수 있음
• 중복 부분 문제(Overlapping Subproblems): 동일한 작은 문제를 여러 번 해결해야 하는 경우

대표적인 DP 문제:

• 최단 경로 문제 (Floyd-Warshall, Bellman-Ford)
• 배낭 문제 (Knapsack Problem)
• 동전 거스름돈 문제 (Coin Change Problem)
• 계단 오르기 문제 (Climbing Stairs)
• 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

---

1. 동전 거스름돈 문제 (Coin Change Problem)

문제 설명

주어진 동전 세트에서 특정 금액을 만들기 위한 최소 동전 개수를 찾는 문제이다. 탐욕적 알고리즘(Greedy Algorithm) 은 항상 최적해를 보장하지 않기 때문에, DP를 활용하여 최적해를 찾는다.

JavaScript 코드:

function coinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

시간 복잡도: O(n × k) (n: 동전 개수, k: 목표 금액)
공간 복잡도: O(k)

---

2. 개구리 점프 문제 (Frog Jump Problem)

문제 설명

개구리가 위치 0에서 k까지 이동하고 싶다. 개구리는 정해진 n개의 점프 거리 를 가질 수 있으며, 점프를 조합하여 k에 도달하는 서로 다른 방법의 수를 구하는 문제이다.

JavaScript 코드:

function frogJump(S, k, q) {
    let dp = new Array(k + 1).fill(0);
    dp[0] = 1;
    
    for (let j = 1; j <= k; j++) {
        for (let s of S) {
            if (s <= j) {
                dp[j] = (dp[j] + dp[j - s]) % q;
            }
        }
    }
    return dp[k];
}

시간 복잡도: O(n × k) (모든 j에 대해 n개의 점프 거리 탐색)
공간 복잡도: O(k) (1차원 배열 사용)

---

3. DP의 메모리 최적화

위 문제에서 2차원 배열이 아니라 1차원 배열을 사용하여 메모리 사용량을 최적화 할 수 있다. 기존의 2차원 dp[i][j] 배열 대신 dp[j]만 유지하면 된다.

JavaScript 코드:

function optimizedCoinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

이러한 최적화를 통해 메모리 사용량을 O(k)로 줄일 수 있다.