그리디 알고리즘(Greedy Algorithm)은 주어진 문제에 대한 최적의 해답을 찾기 위해 사용되는 알고리즘입니다. 이 알고리즘은 문제의 각 부분에서 지역적으로 최적인 해(부분 문제에 대한 최적해)를 선택하는 방식으로 진행되며, 이를 통해 전체 문제의 최적해에 도달할 수 있도록 설계되었습니다.
이번 글에서는 그리디 알고리즘을 활용하여 주어진 금액을 만들 수 있는 최소한의 동전·지폐 개수를 구하는 방법을 다뤄보겠습니다. 이를 위해 사용 가능한 모든 유효한 화폐 단위, 즉 { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } 액면가를 고려하며, 목표 금액을 맞추기 위해 필요한 동전과 지폐의 개수를 반환하는 것이 목표입니다.
몇 가지 예시를 통해 개념을 더 쉽게 이해해 보겠습니다.
예제 1
입력 : 1231
출력 : 7
설명 — 500원권 2장, 100원권 2장, 20원권 1장, 10원권 1장, 1원 동전 1개가 필요합니다. 즉, 2+2+1+1+1 = 총 7개입니다.
예제 2
입력 : 2150
출력 : 3
설명 — 2000원권 1장, 100원권 1장, 50원권 1장이 필요합니다.
그리디 알고리즘 풀이 접근법
이 문제를 그리디 알고리즘으로 해결하려면, 현재 금액에서 사용할 수 있는 가장 큰 액면가를 먼저 찾아야 합니다. 그런 다음 해당 액면가를 금액에서 차감하고, 금액이 0이 될 때까지 이 과정을 반복하면 됩니다. 이렇게 하면 항상 가장 큰 단위부터 사용하게 되어 전체 화폐 개수가 최소화됩니다.
알고리즘 단계
입력: sum (목표 금액)
coins = 0 으로 초기화
1단계: sum보다 작거나 같은 가장 큰 액면가를 찾습니다.
2단계: 해당 액면가를 coins에 추가하고 sum에서 차감합니다.
3단계: sum이 0이 될 때까지 2단계를 반복합니다.
4단계: coins에 저장된 각 값을 출력합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };
int n = sizeof(notes) / sizeof(notes[0]);
void minchange(int sum){
vector<int> coins;
for (int i = n - 1; i >= 0; i--) {
while (sum >= notes[i]) {
sum -= notes[i];
coins.push_back(notes[i]);
}
}
for (int i = 0; i < coins.size(); i++)
cout << coins[i] << "\t";
}
int main(){
int n = 3253;
cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
minchange(n);
return 0;
}
실행 결과
The minimum number of coins/notes that sum up 3253 is
2000 500 500 200 50 2 1
위 실행 결과에서 볼 수 있듯이, 3253이라는 금액은 2000원권 1장, 500원권 2장, 200원권 1장, 50원권 1장, 2원 동전 1개, 1원 동전 1개로 총 7개의 화폐로 표현할 수 있습니다. 이처럼 그리디 알고리즘은 매 순간 가장 큰 단위를 우선적으로 선택함으로써 간결하고 효율적으로 최소 개수의 해답을 도출합니다.