둔필승총

 그리디Greedy 알고리즘은 단순하고 강력한 알고리즘이다.('탐욕법'이라고 불린다.) 그리디 알고리즘은 '매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘'을 의미한다. 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 것이다. 

 하지만 모든 경우에 그리디 알고리즘이 적용되지는 않는다. 그 순간에는 최선일지 몰라도 종합적으로는 그 방법이 최선이 아닐 경우가 있기 때문에 그리디 알고리즘을 모든 경우에 사용가능한 것은 아니다.

그리디 알고리즘을 설명한다면 마시멜로 실험에 비유할 수 있다. 마시멜로 실험은 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 실험이다. 그리디 알고리즘을 사용하면 항상 마시멜로를 1개밖에 받지 못한다. 지금 당장 최선의 선택은 마시멜로 1개를 받는 거지만, 결과적으로는 1분 기다렸다가 2개 받는 게 최선이기 때문이다.  하지만 그리디 알고리즘은 최적해를 보장해주지 못한다.

 그리디 알고리즘은 유형이 다양해서 단순 암기를 통해서 잘 풀 수는 없다.(물론 다익스트라 알고리즘과 같은 유형은 암기가 필요하다)그리디 알고리즘은 미리 외우고 있지 않아도 풀 수 있는 가능성이 있다. 또한 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에 기준이 제시될 가능성이 높다. '가장 큰 순서대로' '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해 준다.

그리디(Greedy) 알고리즘의 대표적인 예시로서는 거스름돈 문제가 있다.

[백준] 거스름돈

https://www.acmicpc.net/problem/5585

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예제 입력 1

380

예제 출력 1

4

출처

Olympiad > 일본정보올림피아드 > 일본정보올림피아드 예선 > JOI 2008 예선 1번

[풀이 과정]

문제에서 '거스름돈 개수가 가장 적게 잔돈을 준다' 라는 조건이 제시되어있다. 입력에서는 620엔을 받아야된다. 620엔에서 일단 제일 큰 단위의 거스름돈부터 차례대로 줄 수 있으면 주는 해결방안을 찾을 수 있다. 

#include <iostream>
using namespace std;

int main()
{
    int input;						//입력값
    cin>>input;							
    int temp = 1000-input;				//동전으로 계산해주어야될 값
    int coin[6] = {500,100,50,10,5,1};  		//동전의 종류
    int result =0;					//거스름돈의 개수
    for(int i=0;i<6;i++)
    {
        result += temp/coin[i];
        temp %= coin[i];
    }
    cout<<result;
}

result에는 temp를 coin[i]로 나눈 몫을 저장해서 더해주고 temp는 coin[i]로 나눈 나머지를 저장해준다. 

 그리디 알고리즘은 input값이 얼마인지는 시간복잡도에 영향을 주지 않는다. 위의 코드를 보았을때 시간복잡도에 영향을 주는 것은 코인의 개수이다. 

 이처럼 그리디 알고리즘은 그 순간의 최적의 해를 고려해준다. 그러나 여기서는 조건에서 coin들이 서로의 배수관계라서 그리디 알고리즘이 적용되었다. 만약 500,100,50,10,5,1 이러한 조합이 아닌 40이나 30같은 서로의 배수관계가 아닌 조합이 있다면 그리디 알고리즘을 적용할 수 없다. 그럴 경우는 예외를 다시 고려해주어야 된다. 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.