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)로 줄일 수 있다.

    반응형

    댓글