😠 그리디 알고리즘(Greedy)
그리디(greedy) 알고리즘은 '현재 상황에서 지금 당장 좋은 것만을 고르는 방법'이다. 현재 주어진 상황에서 가장 좋은 것을 고려하여 문제를 해결해나가며, 현재의 선택이 추후에 미치게 되는 영향은 고려하지 않는다.
현재 주어진 상황에서 가장 좋은 것을 고려해나가도 최적의 해를 구할 수 있는가?
예를 들어, 거스름돈의 최소를 출력하는 프로그램을 작성한다고 가정해보자.
입력은 800 이고 가지고 있는 동전의 종류는 500,100,50 이라고 생각해보자.
거스름돈의 개수가 최소가 되기 위해서, 생각할 수 있는 가장 좋은 조건은 아무래도 큰 단위의 동전부터 소비해나가는 것이다.
" 현재 주어진 상황에서 가장 큰 단위의 동전을 먼저 얼마나 사용해야 하는지 파악하고, 작은 단위의 동전을 사용해보는 방식으로 하자. "
입력 800 에 대하여, 500 -> 100-> 100-> 100 의 순서로 동전을 소비하게 될 것이고, 최종 출력은 4가 나올 것이다.
만일, 우리가 가지고 있는 동전이 500, 400, 100 이라고 가정해보자. 어떠한 결과가 나올까?
동일 입력 800에 대하여, 500->100->100->100 의 순서로 동전을 소비하게 될 것이지만, 이것이 바로 최적의 해일까?
400->400의 순서로 동전을 소비하면 최종 출력이 2가 나온다.
이러한 이유로 그리디 알고리즘을 적용할 때에는 현재 주어진 상황에서 가장 좋은 것을 선택하는 조건을 잘 정한 다음, 이대로 진행해도 최적의 해가 나오는 지, 그리디 알고리즘의 정당성을 확보해야 한다.
거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이기 때문에, 해당 방식으로 진행하면 항상 최적의 해를 보장할 수 있다!
만약, 동전 단위가 무작위인 경우에는 그리디 알고리즘으로 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.
🧧 BOJ 5585 거스름돈
(https://www.acmicpc.net/problem/5585)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 25116 15467 13191 61.311%
문제
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
출력
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
#include <iostream>
int main()
{
int cointype[6] = {500,100,50,10,5,1};
int n;
std::cin>>n;
n=1000-n;
int count = 0;
for(int i = 0 ; i < 6;i++) // 큰 단위의 동전부터 탐색
{
int coin = cointype[i];
count = count + n/coin;
n = n%coin;
}
std::cout<<count;
return 0;
}
