[알고리즘] 그리디(Greedy) 알고리즘

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 를 참고해 작성한 포스트입니다.

Greedy(탐욕적인) 알고리즘

그리디(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법입니다.
Greedy 의 사전적 의미는 “탐욕스러운, 욕심이 많은” 이라는 뜻으로
그리디 알고리즘 대신 탐욕법, 탐욕 알고리즘 등의 이름으로 부르기도 합니다.

이 포스트에서는 탐욕법이라고 부르곘습니다.

[Greedy의 사전적 의미(네이버 영어사전)]

탐욕법은 현재 상황에서 최선의 선택을 하는 것이 핵심입니다.
그렇기 때문에 현재의 선택이 이후 미칠 영향은 고려하지 않습니다.

[탐욕법의 현재 선택을 보여주는 마시멜로 게임]

탐욕법을 사용하는 문제

탐욕법을 사용하는 대표적인 문제는 거스름돈 문제가 있습니다.

한 가게에서 어떤 물건을 계산할 때, N원을 거스름돈으로 받아야 합니다.
가계가 소유한 동전은 500원, 100원, 50원, 10원이 무한대로 있다고 합니다.
이때, 최소한의 동전 수로 거스름돈을 만들 때, 동전의 개수는 몇 개 인가요?
(단, N은 항상 10의 배수입니다.)

이 문제의 해결방법은 높은 화폐 단위부터 낮은 화폐 단위까지 차례대로
최대한 거슬러 주는 방법이 있습니다.

위의 문제에 적용하면 500원을 최대한 많이 거스름돈에 포함시킨 뒤,
남은 거스름돈이 500원보다 작아졌을 때, 100원으로 최대한 많이 포함시키고
다시 남은 거스름돈이 100원보다 작아졌을 때, 50원, 10원을 반복해 최대한 포함시키면서
총 포함시킨 동전의 개수를 세면
최종적으로 최소한으로 사용한 동전의 개수를 알 수 있습니다.

int N = 1760;

int coin_types[4]{500, 100, 50, 10};

int coin_count = 0;
for(int coin : coin_types)
{
    coin_count += (N / coin);   // 최대한 뺀 개수 더하기
    N %= coin;                  // 최선의 선택 후 남은 동전
}

cout << coin_count;

탐욕법 사용 조건

탐욕법은 단순하고 강력하지만, 만능은 아닙니다.
위의 거스름돈 문제에서 모든 동전이 서로 배수 관계에 있었지만
만약, 화폐 단위가 500원, 400뭔, 100원 3가지가 있을 때, 800원을 거슬러 주는 문제에서는
위의 탐욕법을 사용했을 때, 500원 + 100원 + 100원 + 100원으로 총 4개의 동전이 나오지만
최적의 해는 400원 + 400원으로 총 2개의 동전이 나와야 합니다.
따라서 알고리즘 문제에서 탐욕법을 사용하기 전, 탐욕법 사용이 정당한지 검증이 필요합니다.