최소 동전 교환 문제 – 그리디 알고리즘으로 풀기

서로 다른 동전 목록 C(c₁, c₂, …, Cₙ)와 만들어야 할 금액 V가 주어졌을 때, 최소 개수의 동전만 사용하여 V를 만드는 것이 바로 최소 동전 교환(Minimum Coin Change) 문제입니다.

참고: 모든 종류의 동전은 무한개 있다고 가정합니다.

이 문제에서는 동전 집합 C{1, 2, 5, 10}이 주어지며, 각 동전은 무한히 많이 사용할 수 있습니다. 요청된 금액을 만들기 위해 가능한 한 적은 수의 동전을 선택하는 것이 목표입니다.

예를 들어 금액이 22라면 {10, 10, 2}처럼 3개의 동전으로 만드는 것이 최소입니다.

이 알고리즘의 시간 복잡도는 O(V)이며, 여기서 V는 만들어야 할 금액입니다.

입력과 출력

입력:
금액 하나, 예를 들어 47
출력:
Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

알고리즘

findMinCoin(value)

입력 − 거스름돈으로 만들 금액

출력 − 선택된 동전들의 집합

Begin
    동전 집합을 {1, 2, 5, 10}으로 초기화
    큰 단위의 동전부터 작은 단위 순서로 모든 동전 i에 대해 반복:
        while value >= coins[i] do
            value := value – coins[i]
            coin 리스트에 coins[i] 추가
        done
    done
    coin 리스트의 모든 항목 출력
End

핵심 아이디어는 그리디(Greedy) 방식입니다. 가장 큰 단위의 동전부터 우선적으로 사용하여 남은 금액을 줄여 나가면, 전체 동전 개수를 최소화할 수 있습니다.

C++ 예제 코드

#include<iostream>
#include<list>
#define COINS 4
using namespace std;

float coins[COINS] = {1, 2, 5, 10};

void findMinCoin(int cost) {
    list<int> coinList;

    // 큰 단위 동전부터 검사
    for(int i = COINS-1; i>=0; i--) {
        while(cost >= coins[i]) {
            cost -= coins[i];
            coinList.push_back(coins[i]); // 리스트에 동전 추가
        }
    }

    list<int>::iterator it;

    for(it = coinList.begin(); it != coinList.end(); it++) {
        cout << *it << ", ";
    }
}

main() {
    int val;
    cout << "Enter value: ";
    cin >> val;
    cout << "Coins are: ";
    findMinCoin(val);
    cout << endl;
}

실행 결과

Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

금액 47을 입력하면 10원짜리 4개(40원), 5원짜리 1개, 2원짜리 1개를 사용해 총 6개의 동전으로 정확히 47을 만드는 것을 확인할 수 있습니다.

주의할 점

그리디 방식은 {1, 2, 5, 10}처럼 표준적인(canonical) 동전 체계에서는 항상 최적해를 보장하지만, 임의의 동전 체계에서는 실패할 수 있습니다. 예를 들어 동전이 {1, 3, 4}일 때 금액 6을 만들면, 그리디는 {4, 1, 1}(3개)을 선택하지만 실제 최적해는 {3, 3}(2개)입니다. 따라서 일반적인 경우에는 동적 계획법(DP)을 사용하는 것이 안전합니다.