[알고리즘] 탐욕법 (Greedy Algorithm)

[알고리즘] 탐욕법 (Greedy Algorithm)

Tags

Algorithm

탐욕법 (Greedy Algorithm)

개념

현재 상황에서 최선의 선택을 고르는 알고리즘을 말한다. 특정 구조가 있는 알고리즘 이라기 보다, 방법론에 가깝다.

사용처

탐욕법 알고리즘이 최적해를 보장하지는 않는다. 근시적으로 최선의 선택을 고르기 때문에 탐욕법 알고리즘이 도출한 해가 최적해가 될 때 사용한다.

실습

거스름돈 문제

거스름돈을 돈을 줘야 할 때, 돈의 갯수가 적을 수록 좋다. 가능한 가장 큰 단위의 돈 부터 계산하는 것이 보통이다. 이 방법이 곧 최적해이고, 탐욕법과 같고, 이 때 탐욕법이 사용된다 할 수 있다.


// 동전 단위가 500, 100, 50, 10 이고, 입력값이 이 단위만으로 거스름 가능하다 할 때
// 거스름돈을 입력받고 동전 개수를 반환하는 예제
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, ans = 0;
	cin >> n;
	const vector<int> m = {500, 100, 50, 10};

	for (auto i : m) {
		ans += n / i;
		n = n % i;
	}

	cout << ans;
	return 0;
}