[Leet Code Top 100] #322. Coin Change

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

pay[val] 을 val 가격을 지불하는데 필요한 최소 코인 갯수 라고 정의한다면 Dynamic Programming 를 사용할 수 있습니다. pay[코인 중 1개의 가격] = 1 이고 pay[코인1 가격 + 코인2 가격] = 2 이므로 가능한 가격들 중 최소값을 구할 수 있기 때문입니다.

Dynamic Programming 을 사용하면서 묘하게 불필요한 연산이 들어가는 것 같이 느꼈었는데, 지금까지는 거의 DP 풀이를 Top-Down 방식을 사용했고 Memoization 으로 구현했었습니다. 그런데 이번 문제는 Bottom-Up 방식을 사용했고 Tabulation 으로 구현했습니다.

Memoization 은 재귀를 이용하기 때문에 불필요한 계산을 하지 않지만 스택이 과도하게 쌓일 수 있습니다. Tabulation은 스택을 쌓지는 않지만 정답을 구하는데 불필요한 계산을 할 수 있습니다. 두 방식 다 장단점이 있기 때문에 가능하다면 두 가지 방법을 모두 구현하는 것이 좋을 것 같습니다.

 

소스 코드

// Leet Code
// #322. Coin Change
// Success
// Runtime: 572 ms, faster than 6.61% of JavaScript online submissions for Coin Change.
// Memory Usage: 45.2 MB, less than 33.83% of JavaScript online submissions for Coin Change.

function main(){
    // Input // Output
    coins = [1,2,5], amount = 11; // 3
    //coins = [2], amount = 3; // -1
    //coins = [1], amount = 0; // 0
    //coins = [1,3,5], amount = 2; // 2

    console.log(coinChange(coins, amount));
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const pay = new Array(amount + 1).fill(Infinity);

    pay[0] = 0;
    
    for(let idx = 0; idx < coins.length; idx++){
        for(let jdx = coins[idx]; jdx <= amount; jdx++){
            pay[jdx] = Math.min(pay[jdx], pay[jdx - coins[idx]] + 1);
        }
    }
    
    if(pay[amount] === Infinity) return -1;
    return pay[amount];
};

main();

 

더 알아본 내용

var coinChangePractice = function(coins, amount) {

    // pay[val] = n // n is min number of coins that pays val
    const pay = new Array(amount + 1).fill(Infinity);

    // initial setting
    pay[0] = 0;
    
    // 1. duplicate logic
    // for loop contains " pay[coins[idx]] = Math.min(pay[coins[idx]], pay[0] + 1) "
    for(let idx = 1; idx < coins.length; idx++){
        pay[coins[idx]] = 1;
    }
    
    // 2. coin's order doen't matter 
    for(let idx = 0; idx < coins.length; idx++){
    //for(let idx = coins.length - 1; idx >= 0; idx--){ 
    
        // 3. amount's order does matter
        // to cal pay[val], needs pay[0] ~ pay[val-1]
        //                  not pay[val+1] ~ pay[amount]
        for(let jdx = coins[idx]; jdx <= amount; jdx++){
        //for(let jdx = amount; jdx <= coins[idx]; jdx--){
            
            // 4. bottom-up (tabulation)
            pay[jdx] = Math.min(pay[jdx], pay[jdx - coins[idx]] + 1);
        }
    }
    
    // cannot be made up
    if(pay[amount] === Infinity) return -1;
    return pay[amount];
};

1. pay[0] = 0 이라는 조건을 넣지 않았을 때 코인 1개로 만들 수 있는 가격을 pay 에 저장하고 시작했었는데 아래에서 중복이 되면서 불필요한 로직이 되었습니다.
2. pay[jdx - coins[idx]] 에서는 코인을 순회하면서 min 값을 찾을 뿐이므로 코인의 순서는 관계 없습니다.
3. bottom-up 방식으로 순회하며 pay[0] ~ pay[val-1] 까지의 값이 있어야지만 pay[val] 에 들어가는 최소의 코인 갯수를 구할 수 있습니다. 따라서 amount 까지 순회할 때의 순서가 바뀌면 안됩니다.
4. bottom-up 방식으로 구현했기 때문에 가능한 모든 값을 기록하는 Tabulation 방식을 사용합니다.

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - JavaScript Using DP Memoization and Tabulation
• 알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)