동전 거스름돈으로 알아보는 탐욕 알고리즘 (Greedy Algorithm)

탐욕적 기법이란?

작은 선택의 순간에 가장 이익이 되는 선택을 내려서 전체적인 결과에서 최적의 해를 구하는 프로그래밍 기법

동적 계획법(Dynamic Programming)으로도 최적화 문제를 해결하기 위한 방법으로 사용할 수 있지만,

동적 계획법은 보다 일반적이고 완전한 최적해를 찾는다면 탐욕적 기법은 간편하고 빠르게 근사해를 구하는데 유용하다.

 

동전 거스름돈 문제

가게에서 500원, 100원, 50원, 10원짜리 동전을 사용하고 있을 때 손님이 받아야할 거스름돈이 760원이라면

가장 적은 동전의 개수로 거스름돈을 주려면 어떻게 해야할까?

 

값이 가장 큰 동전부터 사용할 수 있는지 확인하면 된다.

가장 큰 동전 500원이 760원보다 작기 때문에 500원부터 차례대로 살펴보기

동전	개수	남은 돈
500원	1	260원
100원	2	60원
50원	1	10원
10원	1	0원

 

이런식으로 동전 5개로 760원을 만들 수 있다.

이를 코드로 표현하면

function greedy(n) {
  let coins = [10, 50, 100, 500];
  coins.sort((a, b) => b - a); // 동전을 큰 순서대로 정렬

  let coinCount = 0;

  for (let coin of coins) {
    const count = Math.floor(n / coin); // 현재 동전으로 얼마나 많이 거슬러 줄 수 있는지 현재 금액을 coin으로 나누기
    coinCount += count; // 동전 개수 더하기
    n -= count * coin; // 남은 금액 업데이트

    if (n === 0) {
      break;
    }
  }
  return coinCount;
}

동전을 큰 순서대로 정렬 후 각 동전으로 얼마나 많이 거슬러 줄 수 있는지 계산하여 최소한의 동전개수를 찾는다.

 

탐욕적 기법의 한계

동전이 1원, 7원, 9원, 11원, 100원이라고 가정할 때 16운을 만들기 위한 최소한의 동전은 몇개일까?

 

탐욕적 기법을 사용하면 가장 큰 단위의 동전인 11원 1개 1원 5개로 총 6개가 필요하다.

하지만 16원은 9원짜리 1개, 7원짜리 1개 총 2개의 동전으로도 만들 수 있다.

 

그렇기 때문에 탐욕법은 항상 최적의 해를 찾아내는 것은 보장되지 않을 수 있다.