Greedy Algorithm

그리디 알고리즘

최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달.

그리디 알고리즘의 문제

문제: 12100원을 지불하기 위한 최적의 화폐 사용 방법을 찾기

코드

#include<bits/stdc++.h>
using namespace std;
int ret, totalAmount = 12100;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<pair<int,int>> currency = {{10000,5},{5000,5},{1000,5},{100,5}};

    // 내림차순으로 정렬
    sort(currency.rbegin(), currency.rend());

    // debugging
    for(auto i : currency){
        cout << i.first << " " << i.second << ' ';
    }

    for(auto c : currency){
        while(totalAmount >= c.first){
            totalAmount -= c.first;
            c.second--;
            ret++;
        }
    }
    if(totalAmount == 0){
        cout << ret << '\n';
    } else {
        cout << "불가능 합니다." << '\n';
    }

    return 0;
    

문제는 10000원 5장, 5000원 5장, 1000원 5장, 100원 5개가 있다. 화폐의 단위가 큰 것부터 사용하기 위해서 내림차순으로 정렬을 하고 벡터를 순회하면서 첫번 째 반복에서 12100- 10000을 차감하고 ret을 1증가 2100은 5000보다 작으므로 5000단위는 사용할 수 없다. 1000원 단위는 사용할 수 있으므로 2100 - 2000 = 100이 되고 100원 단위도 사용할 수 있으므로 100이 되서 ret은 총 4번 증가하게 된다.

Reference

나의 뇌