[알고리즘] 그리디 알고리즘(Greedy Algorithm) - 거스름돈 문제로 이해하기

오늘은 알고리즘 기법 중 하나인 그리디 알고리즘(Greedy Algorithm) 에 대해 알아보자.

재밌는 이름을 가지고 있는 알고리즘 기법이다.
그리디 알고리즘이라니, 그리디한 게 뭘까?

그리디(greedy)하다는 것은 탐욕스럽다 , 욕심이 많다 라는 의미를 담고 있다.
따라서 그리디 알고리즘(Greedy Algorithm) 이라 함은 탐욕스러운 알고리즘 , 욕심 많은 알고리즘 이라는 뜻이 되겠다.

그리디 알고리즘은 욕심이 아주 많기 때문에 현재 입장에서 가장 이득이 되는 행동을 반복한다.
혹은 현재 입장에서 가장 최선이 되는 행동을 반복한다.

알고리즘 기법은 간단 명료하다.
하지만 그리디 알고리즘으로 최적해(optimal solution) 를 구할 수 있는 문제는 드물다. 그럴 것 같지 않은가?
매 순간 가장 좋아 보이는 선택만을 했을 뿐인데 정말로 가장 좋은 해가 되다니, 놀라운 일이다.

매 순간의 선택, 즉 locally optimal한 모든 선택이 최적해에 포함되어야 하기 때문에 그리디 알고리즘으로 최적해를 구할 수 있는 경우는 드물고, 구했다 하더라도 구한 최적해가 정말 최적해인지 증명해야 한다.

그럼에도 불구하고, 그리디 알고리즘으로 해결할 수 있는 문제들이 있어서 간단하게 소개해보려고 한다.

문제: 최소 개수의 화폐로 잔돈 거슬러 주기

첫 번째 문제는, 최소 개수의 화폐로 잔돈을 거슬러 주는 문제이다.

어떤 가게에서 판매하는 물건의 가격이 8,230원일 때, 손님이 해당 물건을 구매하면서 10,000원짜리 지폐 1장을 지불하였다.
이때 최소 개수의 화폐로 잔돈을 거슬러 주려면 어떻게 줘야 할까?

현재 거스름돈에서 거슬러 줄 수 있는 가장 큰 단위의 화폐를 최대한 많이 골라가면서 잔돈을 거슬러 주면 된다.
생각해 볼 수 있는 화폐 단위로는 1,000원, 500원, 100원, 50원, 10원이 있다.

그리디한 방식

• 1,000원 -> 1장 사용 -> 남은 금액 770원
  
• 500원 -> 1개 사용 -> 남은 금액 270원
  
• 100원 -> 2개 사용 -> 남은 금액 70원
  
• 50원 -> 1개 사용 -> 남은 금액 20원
  
• 10원 -> 2개 사용 -> 남은 금액 0원
  
  

따라서 최소 개수의 화폐로 잔돈을 거슬러 주려면 1,000원 1장, 500원 1개, 100원 2개, 50원 1개, 10원 2개를 돈통에서 꺼내 손님에게 주면 된다.

여기서 “1,000원 1장, 500원 1개, 100원 2개, 50원 1개, 10원 2개”라는 최적해를 구하기 위해서 한 짓은 지금 당장 가장 큰 단위의 화폐를 최대한 고른 것밖에 없다.

하지만 잔돈을 거슬러 주는 문제에 대해서도, 어떤 나라에서는 그리디하게 잔돈을 골랐을 때 거스름돈이 맞지 않을 수도 있다는 점을 생각해야 한다.

재밌는 알고리즘인 것은 분명하다.
관련하여 백준(boj.kr)에 유사한 문제가 있어 가져와봤다.

https://www.acmicpc.net/problem/2720

앞서 소개한 문제인 거스름돈 주는 문제이다.
이 문제에 그리디 알고리즘을 적용하면 아주 쉽게 문제를 해결할 수 있다.

[C++]

#include <iostream>
using namespace std;

int main() {
    int T, C;
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> C;

        int quarter = C / 25;
        C %= 25;

        int dime = C / 10;
        C %= 10;

        int nickel = C / 5;
        C %= 5;

        int penny = C;

        cout << quarter << " " << dime << " " << nickel << " " << penny << "\n";
    }

    return 0;
}

T번 만큼 거스름돈을 줘야 하므로 T번 반복한다.
거스름돈 C를 입력받고, 가장 큰 단위부터 차례로 쿼터, 다임, 니켈, 페니를 구한다.
뒤의 단계는 생각할 필요 없이 그리디하게 하나씩 구해나가면 문제가 해결되어 있다.

이외에도, 그리디 알고리즘으로 최적해를 구할 수 있는 여러 문제들이 있는데 다음 포스팅에는 최소 신장 트리(Minimum Spanning Tree)라는 주제를 다뤄볼까 한다.