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

그리디 알고리즘이란?

• Greedy는 탐욕적인 이라는 뜻을 가진 영어입니다.
• 즉, 순간순간 최선의 선택을 하는 알고리즘이라는 것입니다.
• 그리디 알고리즘은 근시안적인 알고리즘으로
  보통은 프로그래머가 생각한 그대로 문제를 풀 때 사용되는 알고리즘입니다.
• 그리디 알고리즘은 빠른 풀이가 가능하다는 장점이 있지만 항상 정답이 되지는 않는다는 단점이 있습니다.

---

예시문제 - 5585) 거스름돈

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

해당 문제는 1000엔에서 물건값을 뺀 후
받을 수 있는 잔돈의 최소 개수를 구하는 문제이다.

최소 동전 개수 문제는 가장 큰 동전부터 가능한 개수를 구해서 다 더하면 답이 나온다.

#include <iostream>
using namespace std;

int main(){
	int N; cin>>N;
    N = 1000 - N;
    int answer = 0;
    int num[] = {500,100,50,10,5,1};
    for(int n : num){
    	answer += (N/n);
        N %= n;
    }
    cout<<answer<<endl;
    return 0;
}

이렇게 순간순간의 최적해를 구하는 문제가 그리디 문제이다.