그리디(Greedy) 알고리즘이란?

Greedy Algorithms(탐욕법, 탐욕 알고리즘)

: 문제 해결 과정에서 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행, 최종 해답에 도달하는 문제 해결 방식이다. 당장 눈앞에 보이는 최적의 상황만을 쫓는다. 

 

문제를 풀며 이해해보자. 

거스름돈(BOJ 5585번)

전형적인 그리디 알고리즘 문제 !

#include <iostream>
using namespace std;

int main()
{
	int n; cin >> n; // 잔돈
	n = 1000 - n;
	int result = 0; //잔돈의 개수

	result += n / 500; // 500원 개수
	n %= 500;
	result += n / 100;
	n %= 100;
	result += n / 50;
	n %= 50;
	result += n / 10;
	n %= 10;
	result += n / 5;
	n %= 5;
	result += n;

	cout << result << endl;

	return 0;
}

이렇게 result와 n을 계속 변화시키며 상황에 맞게 잔돈의 개수를 더하면 된다!

이렇게, 매 순간에 대해 최적인 선택을 하면서 result 값을 구해주는 것이다.