그리디

 

그리디란?

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘이다. 또는 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.

 

 

 이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.

2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.

3. 구현해서 문제를 통과한다.

 

 

현실적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.

2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿을 가진다.

3. 믿음을 가지고 구현해서 문제를 통과한다.

 

 

바로 연습문제를 통해 그리디 알고리즘을 맛을 보겠다.

 

---

 

BOJ 11047번 : 동전 0 문제이다.

 

우리가 구현하고자 하는 것은 동전을 최소로 소모하면서 물겂값을 지불하는것이다.

우리는 50, 100 원의 갯수를 5개 이상 소모하지 않으면서 최대한 금액이 큰 값을 지불할 수 있으면 그것을 지불한 후에 그보다 작은 금액들을 사용함으로서 동전의 갯수를 최소화할 수 있다는 사실을 알 수 있다.

 

실제 구현 코드이다.

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;
int a[15];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n , k;
	cin >> n >> k;

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = n - 1; i >= 0; i--)
	{
		ans += k / a[i];
		k %= a[i];
	}

	cout << ans;
}

 

---

BOJ 1931 : 회의실 배정 문제이다

 

그리디 파트에서 task sheduling problem 이라는 이름으로 꼭 다루는 문제라고 한다.

 

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;
pair<int, int> r[100000];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {

	cin >> r[i].second >> r[i].first;
	}
	sort(r, r + n);

	int ans = 0;
	int t = 0;

	for (int i = 0; i < n; i++)
	{
		if (t > r[i].second) continue;
		ans++;
		t = r[i].first;
	}

	cout << ans;
}