[알고리즘] 5. 탐욕법(Greedy)

"당장 최선의 수를 고려하기"

 

탐욕 알고리즘은 매 선택마다 당장의 최선의 선택을 하여 답에 도달하는 방법이다.

항상 최선의 결과를 보여주지는 않지만 특정 상황들 속에서는 굉장히 효과적이고, 직관적이다.

 

대표적인 예시로는, 거스름돈이 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int input;
int wons[4] = {500, 100, 50, 10};

vector<int> calc_coin(int money)
{
    vector<int> coins = vector<int>(4);
    coins[0] = money / 500;
    coins[1] = (money % 500) / 100;
    coins[2] = (money % 100) / 50;
    coins[3] = (money % 50) / 10;

    return coins;
}

int main()
{
    cout << "**잔돈 드립니다**" << endl;
    cout << "얼마를 드릴까요? : ";
    cin >> input;
    vector<int> amount = calc_coin(input);
    for (int i = 0; i < 4; i++)
    {
        cout << wons[i] << "원 : " << amount.at(i) << "개" << endl;
    }
    return 0;
}



**잔돈 드립니다**
얼마를 드릴까요? : 1480
500원 : 2개
100원 : 4개
50원 : 1개
10원 : 3개

가장 큰 500원짜리부터 최대한 준 뒤, 그 다음인 100원짜리를 가능한 많이 주고, 그 이후 50원과 10원도 같은 방식으로 한다.

이와 같이, 당장의 최선의 선택을 하는 방법이 탐욕법이다.