[C/C++]탐욕 알고리즘(그리디 알고리즘) - greedy algorithm

탐욕 알고리즘(그리디 알고리즘)

 

탐욕 알고리즘 또는 그리디 알고리즘 이라는 것에 대해서 이야기 해봅시다. 

탐욕 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법입니다.

 

매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지는 않습니다.

그리디 알고리즘이 제대로 동작하지 않은 예시로 주로 드는 것은 마쉬멜로우 실험입니다.

 

예를 들어서, 지금 당장에 마쉬멜로우 1개를 받을 수 있지만, 10분을 기다린 경우 2개의 마쉬멜로우를 받을 수 있는 실험이 있다고 가정해 봅시다. 그리디 알고리즘으로는 지금 당장 1개를 선택하겠지만, 전체로 본다면 10분을 기다린 후에 2개의 마쉬멜로우를 받는게 가장 많은 마쉬멜로우를 받을 수 있을 것 입니다.

 

그리디 알고리즘은 100% 최적의 해를 보장하지는 않지만, 계산 속도가 최적의 해를 보장하는 알고리즘에 비해서 빠른 경우가 많습니다.

 

그리디 알고리즘은 지금의 선택이 다음 선택에 영향을 미치지 않는 경우에 사용하면 유용합니다.

즉, 매 순간마다의 선택이 전체 결과에 서로 독립적인 경우라고 할 수 있습니다.

그림으로 예시를 들어보겠습니다.

 

 

A에서 B를 거쳐서 C로 가는 경로의 최소 거리를 구해 봅시다.

A에서 B, B에서 C로 가는 경로는 각각 서로 영향을 미치지 않습니다. 이런 문제를 해결하는 경우에 그리디 알고리즘은 좋은 선택이 됩니다.

 

i) A에서 B까지 최단거리는 (B) 2m

ii) B에서 C까지 최단거리는 (2) 2m

결과) i에서의 선택 + ii에서의 선택 = 4m

 

각각의 경우에서 최선의 선택을 해서 최단 경로는 4m인 것을 구 할 수 있습니다.

 

거스름돈 문제

 

이제 실전에 한번 들어가 봅시다. 그리디 알고리즘 문제를 보면 거의 항상 나오는 베스트셀러입니다.

백준에 있는 거스름돈 문제를 한번 풀어 봅시다.

 

출처 링크 : https://www.acmicpc.net/problem/5585

5585번: 거스름돈

문제의 간략한 설명)

가게에는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔 거스름돈이 충분히 있다고 하자.

1000엔 지폐로 물건을 사고 거스름돈을 준다고 했을 때,  잔돈을 가장 적게 주는 경우의 개수를 구해보자.

문제 풀이 아이디어)

어떻게 해결하면 좋을지 생각해 봅시다. 잔돈을 가장 적게 주려고 한다면,

가장 단위가 큰 동전을 줄 수 있는 만큼 주고, 그 다음으로 큰 단위의 동전을 순차적으로 거슬러 주면 됩니다.

 

매 순간 어떤 동전을 거스름돈으로 줘야 할지 선택을 해야 할 때, 그 순간 줄 수 있는 가장 큰 단위의 동전을 거스름돈으로 주면 됩니다. 코드로 구현해 보면 아래와 같습니다.

 

#include<iostream>
using namespace std;
int main()
{
    int Pay;
    int result=0;
    cin >> Pay;
    
    Pay = 1000 - Pay;
 
    result += Pay / 500;
    Pay %= 500;
    result += Pay / 100;
    Pay %= 100;
    result += Pay / 50;
    Pay %= 50;
    result += Pay / 10;
    Pay %= 10;
    result += Pay / 5;
    Pay %= 5;
    result += Pay / 1;
    
    cout << result << endl;
    
    return 0;
}

코드 설명)

5~9 줄 코드) Pay에 지불해야 할 돈을 입력받고, 9번째 줄에 Pay에 거슬러 줘야할 총 거스름돈의 액수를 입력했습니다.

 

11~21줄 코드) 11번 째 줄을 보면, Pay/500을 통해서 거슬러 줄 수 있는 500엔의 최대 개수를 구하고, 12번째 코드를 통해서 500엔을 이미 지불 했으므로 지불할 남은 액수를 구하기 위해서 500으로 나눠줬습니다. 나머지 아래도 동일한 이유입니다.

---

설명하는게 익숙하지가 않아서, 이런 글을 쓰는게 어색하네요.

혹시 보다가 잘못된 부분이나 질문이 있다면,

댓글로 남겨주세요.