1. 그리디 알고리즘

당장 좋은 것만 선택하는 그리디

단순 무식하게 탐욕적으로 문제를 푸는 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

정렬+그리디 -> 자주 출제

예제 3-1. 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

#include <iostream>
using namespace std;

int main()
{
	int n, cnt = 0;
	cin >> n;
	int coin_types[4] = { 500,100,50,10 };
	for (int i = 0; i < 4; i++)
	{
		cnt += n / coin_types[i];
		n %= coin_types[i];
	}
	cout << cnt;
}

실제로 거스름돈 문제에서 동전(화폐)의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로는 해결할 수 없다.
다이나믹 프로그래밍으로 해결 가능