JavaScript 알고리즘 - 탐욕법(Greedy)

탐욕(greedy) 알고리즘이란 현재 상황에서 당장 가장 좋아보이는 상황만 선택하는 알고리즘입니다. 그리디 알고리즘 또는 탐욕 알고리즘이라고 부르며 최적의 결과값을 구하기 위한 근사적인 방법으로 사용될 때가 많습니다.

많은 경우에서는 단순한 탐욕 알고리즘 만으로는 최적의 결과값을 놓칠 수 있습니다. 하지만 최적의 값과 가까운 값을 뱉는 것을 고려하면 다양한 프로그램에서 "근사값"을 구하는 목적으로 사용되곤 합니다.

(예시 문제) 거스름 돈 문제
카운터에 500원, 100원, 50원, 10원짜리 동전이 무수히 많이 존재할 때
6,480원을 거슬러 주어야 할 때, 동전 개수의 최소값은?

// 처음에 푼 풀이

function solution(nums) {
  let answer = 0;
  while (nums > 0) {
    if (nums >= 500) {
      answer += 1;
      nums = nums - 500;
    } else if (nums >= 100 && nums < 500) {
      answer += 1;
      nums = nums - 100;
    } else if (nums >= 50 && nums < 100) {
      answer += 1;
      nums = nums - 50;
    } else if (nums >= 10 && nums < 50) {
      answer += 1;
      nums = nums - 10;
    }
  }
  return answer;
}

// 수정한 코드

function solution(nums) {
  let count = 0;
  const arr = [500, 100, 50, 10, 5, 1];
  for (let item of arr) {
    count = count + Math.floor(nums / item); //동전의 개수
    nums = nums - item * Math.floor(nums / item); // 남은 돈 계산
  }
  return count;
}

예를 들어 6,480원의 거스름 돈을 500원, 100원, 50원, 10원짜리 동전으로 최소한의 개수를 들여 거슬러 주어야 할 때 500원 x 12개 + 100원 x 4개 + 50원 x 1개 + 10원 x 3개 총 20개의 동전이 필요하게 됩니다.

이렇게 단순히 큰 화폐 단위부터 선택하여 최적의 값을 구할 수 있는 이유는 각 화폐 단위가 배수 관계에 속하기 때문입니다.

하지만 만약 120원을 거슬러 주어야 할 때 80원, 60원, 10원 단위의 동전으로 거슬러 주어야 하는 문제가 있습니다. 이때 60원 x 2개 = 120원 으로 최소 2개만 사용할 수 있는 최적의 결과값이 있지만 탐욕법으로 풀게되면 80원 부터 사용하기 때문에 80원 x 1개 + 10원 x 4개 총 5개의 동전이 필요하게 됩니다.

따라서 탐욕법을 사용할 때에는 정당성 분석을 거쳐서 최적의 값을 구해야 합니다.