자바스크립트로 구현한 탐욕 알고리즘 (greedy algorithm in javascript)

탐욕 알고리즘이란?

탐욕 알고리즘이란 매 선택의 순간에 그 순간에서의 가장 최적의 해를 도출해내는 알고리즘입니다. 한가지 예시로 거스름 돈 교환을 들 수 있는데 만약 10, 7, 5, 1로 구성되어 있는 동전들로 14를 교환해준다고 했을 때, 탐욕 알고리즘을 사용하면 10 - 1개 1 - 4개로 구성될 것이다. 왜냐하면 탐욕 알고리즘은 해당 순간에 가장 최선의 해를 내는 알고리즘이기 때문이다. 하지만, 전체적으로 봤을 때 최선의 해라고 볼 수 없다. 왜냐하면 7 - 2개로 구성하는 것이 가장 최선의 해답이기 때문이다. 예시를 보면 알 수 있듯이 매 순간 최선의 선택을 했다고해서 종합적으로 봤을 때에 최선의 선택이라고는 볼 수 없다.

간단한 자바스크립트 예시

// greedy algorithm (거스름 돈 문제)
// 10000 5000 1000 500 100 50 10
function getChange(value) {
  let changes = [10000, 5000, 1000, 500, 100, 50, 10];
  let won = Math.floor(value / 10) * 10; // 1의 자리 원화 반내림
  let i = 0;
  let counts = [];

  while (true) {
    if (won >= changes[i]) {
      let count = Math.floor(won / changes[i]);
      won = won - changes[i] * count;
      counts[i] = count;
    } else {
      counts[i] = 0;
    }

    i++;
    if (won === 0) {
      for (let j = 0; j < changes.length - i; j++) {
        counts.push(0);
      }
      break;
    }
  }

  changes.map((change, index) => {
    console.log(`${change.toLocaleString()}원 ${counts[index]}개`);
  });
}

getChange(32660);
/*
10,000원 3개
5,000원 0개
1,000원 2개
500원 1개
100원 1개
50원 1개
10원 1개
*/
getChange(1000);
/*
10,000원 0개
5,000원 0개
1,000원 1개
500원 0개
100원 0개
50원 0개
10원 0개
*/
getChange(1500);
/*
10,000원 0개
5,000원 0개
1,000원 1개
500원 1개
100원 0개
50원 0개
10원 0개
*/
getChange(10100);
/*
10,000원 1개
5,000원 0개
1,000원 0개
500원 0개
100원 1개
50원 0개
10원 0개
*/
getChange(1500000);
/*
10,000원 150개
5,000원 0개
1,000원 0개
500원 0개
100원 0개
50원 0개
10원 0개
*/
getChange(9999);
/*
10,000원 0개
5,000원 1개
1,000원 4개
500원 1개
100원 4개
50원 1개
10원 4개
*/