Greedy Algorithm

 

Greedy Algorithm, 탐욕알고리즘

• 정의 : 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘
• 특징 : 탐욕알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

예시코드

// boj - 5585 : greedy algorithm

#include<iostream>
using namespace std;

int main() {
	int monney;
	cin >> monney;
	monney = 1000 - monney;
	int res = 0;

	// 500
	int p = monney / 500;
	res += p;
	monney -= (500 * p);

	// 100
	p = monney / 100;
	res += p;
	monney -= (100 * p);

	// 50
	p = monney / 50;
	res += p;
	monney -= (50 * p);

	// 10
	p = monney / 10;
	res += p;
	monney -= (10 * p);

	// 5
	p = monney / 5;
	res += p;
	monney -= (5 * p);

	// 1
	p = monney / 1;
	res += p;
	monney -= (1 * p);

	cout << res << endl;
	return 0;
}