[javascript] 심심해서 만들어본 잔돈 교환 함수(coin-change function)

서문 

 

알고리즘 수업이 생각보다 난이도있게 흘러가고, 양방향 수업 부재로 인한 질의 응답이 어려워서 간단한 알고리즘들은 직접 구현해보며 만들어가는 것이 좋을 듯 생각이 들었다. 물론 꾸준히 업데이트 할 수 있을지는 미지수이지만 할만하다 싶은 부분들은 새롭게 올리는 것이 괜찮을 듯 싶다. 

 

알고리즘 

동전교환 알고리즘은 Greedy 알고리즘을 사용하여, 순간 순간 최적의 해를 선택하여 문제를 해결하는 방법이다. 여기서 문제란 현재 주어야 하는 잔돈에서 내가 어떤 조합으로 잔돈을 거슬러 줄 것인가이다. 그럼 여기서 순간순간 최적의 해란 ? 각 화폐 및 동전마다 최소의 수량을 결정하는 것이다. 

 

우리가 약 95420원의 잔돈을 손님에게 전달해준다고 가정하자. 우리는 먼저 가장 큰 화폐권부터 계산을 할 것이다. 한국의 화폐는 [50000,10000,5000,1000,500,100,50,10] 가 있으니, 50000원 부터 계산을 하자. 50000원권은 95420 / 50000 (소수점 자리 버림) >= 1을 만족하니, 50000원 권은 1개만 건네어 주면되고 나머지 잔돈은 45420원이 된다. 이후 10000원권을 계산해보면 45420/10000 >= 1 을 만족하니 4개를 전달 하면되고, 5000원 또한 5420/5000 >= 1을 만족하니 1개를 전달하면된다. 그러나, 500원은 420 >= 1 을 만족하지 못하기 때문에 0개가 된다. 이런 알고리즘을 사용하여, 100원자리는 4개 , 50원짜리는 0개 10원짜리는 1개의 전체 잔돈의 수량이 결정된다. 

 

코드

물론 우리는 실생활에서 이 알고리즘을 너무 잘 사용하고 있어 굳이 언급하지 않아도 충분히 문제를 해결할 수 있지만, 우리는 어떻게 이 풀이 방법을 컴퓨터에게 알려주어야 할까 ? 

function coinChange(money) {
    const coins = [50000, 10000, 5000, 1000, 500, 100, 50, 10];

    const change = [];
    for (let i = 0; money !== 0; i++) {

        const count = money / coins[i] >= 1 ? Math.floor(money/coins[i]) : 0 ;
        change[i] = {
            value: coins[i],
            count: count
        }

        money = count > 0 ? money -= coins[i] * count : money;
    }

    return change;
}

console.log(coinChange(405620));

 

그리디 알고리즘의 한계

그리디 알고리즘이 쉽고 빠르게 입력할 수 있는 알고리즘이지만, 단점이 존재한다면 설정한 조건은 두번 다시 변경할 수 없다는 점과 항상 최적의 해를 제공해 줄 수 없다는 점이다.

 

예를 들어 우리나라 화폐체계에 110원짜리 동전이 없지만 존재한다고 가정하자. 그리디 알고리즘을적용하여 920원의 잔돈이 발생한다면 500원은 1개, 110원은 3개, 100원은 0개, 50원은 1개, 10원은 4개로 총 9개의 동전을  전달해야 한다. 110원짜리가 존재하지 않다면 500원은 1개 100원은 4개 10원은 2개로 총 6개의 잔돈이 발생한다. 이 처럼 그리디 알고리즘은 항상 최적의 해를 전달해주는 것이 아니고 문제에 따라 최적해에 가까운 근사해를 제공해준다.