Greedy Algorithm (욕심쟁이 기법)과 동전 교환 문제

지즈·2025년 5월 14일

알고리즘

목록 보기

3/6

1. 탐욕 알고리즘이란?

탐욕 알고리즘(Greedy Algorithm)은 현재 상황에서 가장 최선으로 보이는 선택을 반복하여 문제를 해결하는 방식이다.
과거의 선택이나 미래의 가능성을 고려하지 않고, 지금 당장 최선의 선택을 하는 것이 핵심이다.

현재의 선택이 항상 전체 최적해로 이어질 수 있는 문제에서만 올바르게 동작한다.

2. 동전 교환 문제 예제

문제 설명
동전 단위: {1원, 5원, 10원, 50원, 100원}

목표: 378원을 가장 적은 수의 동전으로 구성하라

알고리즘 설계 방식
사용할 동전 집합 G는 공집합에서 시작한다.

동전 집합에서 가장 액수가 큰 동전부터 가능한 만큼 선택한다.

현재 남은 금액에서 해당 동전의 금액만큼 차감하고, 다시 다음 동전으로 반복한다.

목표 금액이 될 때까지 반복한다.

예시 풀이

현재 금액: 378원
동전 선택 순서: 100 → 50 → 25 → 10 → 5 → 1

100원 3개 선택 → 남은 금액: 78
50원 1개 선택 → 남은 금액: 28
25원 1개 선택 → 남은 금액: 3
1원 3개 선택 → 완료

결과

총 동전 개수: 8개

사용한 동전: 100x3, 50x1, 25x1, 1x3

3. 탐욕 알고리즘 절차

step.1 선택 (Selection)

조건을 만족하는 최선의 원소를 고른다.

step.2 가능성 검사 (Feasibility)

선택한 원소를 포함한 현재 상태가 유효한지를 판단한다.

step.3 솔루션 검사 (Solution Check)

현재 선택한 집합이 문제의 해인지 확인한다.
아니라면 다시 1단계로 돌아가 반복한다.

탐욕 알고리즘은 항상 최적의 해를 보장하지 않는다.
이 방식이 적용 가능한 경우는 다음과 같다:

동전 단위가 서로 배수 관계일 때

최적 부분 구조 (Optimal Substructure)를 만족할 때

탐욕 선택 속성 (Greedy-choice property)를 만족할 때

예를 들어 {1, 4, 5} 단위에서 6원을 만들 경우,
탐욕적으로 5 + 1을 선택하면 비효율적이지만, 실제 최적해는 3 + 3이다.

5. C++ 코드

#include <iostream>
#include <vector>

std::vector<int> coins = {100, 50, 25, 10, 5, 1};
std::vector<int> coinCounts;

void getMinimumCoins(int k, int &totalCoins) {
    coinCounts.resize(coins.size(), 0);
    totalCoins = 0;
    int currentAmount = 0, i = 0;
    
    while (currentAmount < k)
    {
        int coin = coins[i];
        if (currentAmount + coin <= k) 
        {
            coinCounts[i]++;
            totalCoins++;
            currentAmount += coin;
        }
        else i++;
    }
}

int main() {
    int k;
    std::cin >> k;
    int count;
    
    getMinimumCoins(k, count);
    std::cout << count << "\n";

    for (size_t i = 0; i < coins.size(); ++i)
    {
        if (coinCounts[i] > 0)
            std::cout << coins[i] << "원: " << coinCounts[i] << "개\n";
    }
    
    return 0;
}