[0x11] 그리디

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘.

관찰을 통해 탐색 범위를 줄이는 알고리즘 이라고도 볼 수 있다.

병합 정렬도 그리디의 일종이다.

 

이상적인 풀이 흐름

 

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

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

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

 

코딩테스트에서의 추천 전략

 

거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다

-> 구현 후 제출해보고 틀리면 바로 손절

 

100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다

-> 일단 넘어가고 다른 문제를 풀게 없거나 종료까지 20~40분정도 남은 시점에 코딩을 시작

 

그리디 문제를 못 푸는 것 보다 오히려 그리디로 푸는 문제가 아닌데 그리디로 풀 수 있다고 착각하는걸 더 조심해야 한다.

 

귀류법으로 명제의 참거짓 여부를 판단하는것이 좋다.

지금 당장 손해를 보더라도 나중에 가서 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인하거나 반례를 찾을 때 도움이 된다.

 

연습 문제

 

11047: 동전 0

#include <iostream>

using namespace std;

int arr[11];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, k, answer = 0;
	cin >> n >> k;

	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	for (int i = n - 1; i >= 0; --i)
	{
		answer += k / arr[i];
		k %= arr[i];
	}

	cout << answer;

	return 0;
}

 

1931: 회의실 배정

#include <iostream>
#include <algorithm>

using namespace std;

pair<int, int> arr[100001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, answer = 0, t = 0;
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		// custom cmp 함수를 안만들기 위해 종료시간을 first로 둠
		cin >> arr[i].second >> arr[i].first;
	}

	sort(arr, arr + n);

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

	cout << answer;

	return 0;
}

 

종료시간이 짧은 순으로 정렬해야 하기 때문에 cmp함수를 따로 만들지 않기 위해 first와 second를 반대로 입력 받았다.

 

2217: 로프

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, answer = 0;
	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	
	sort(arr, arr + n);

	// 현재 로프의 최대중량 무게에서 로프 개수만큼 곱하면 로프가 버틸수 있는 최대무게가 됨
	for (int i = 1; i <= n; ++i)
		answer = max(answer, arr[n - i] * i);

	cout << answer;

	return 0;
}

 

n개의 로프에서 k개를 고른다고 하면 최대중량이 높은걸 k개 고르면 된다.

 

1026: 보물

#include <iostream>
#include <algorithm>

using namespace std;

int arrA[51];
int arrB[51];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, answer = 0;
	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> arrA[i];
	for (int i = 0; i < n; ++i)
		cin >> arrB[i];

	sort(arrA, arrA + n);
	sort(arrB, arrB + n);

	for (int i = 0; i < n; ++i)
		answer += arrA[i] * arrB[n-i-1];

	cout << answer;

	return 0;
}

 

재배열 부등식으로 증명이 가능하다.

큰 원소와 큰 원소를 매칭 시켜주면 결과가 최대가 되고, 큰 원소와 작은 원소를 매칭 시켜주면 결과가 최소가 된다는 부등식이다.

 

그리고 문제의 조건에 "단, B에 있는 수는 재배열하면 안 된다." 라고 되어있는데 전혀 상관이 없다.

A만 재배열할 때의 답을 구하는 것이 A,B 둘 다 재배열할 때의 답을 구하는 것과 동치임을 알아낼 수 있는가에 대한 것을 시험하는 것도 포함되어 있다고 볼 수 있다.

 

문제에서 특정 라이브러리를 쓰지 못하게 막거나 시간, 메모리에 제한을 두는것 빼고는 특정 방법을 사용해서 풀라고 강요하지 않고 강요할 방법도 없다.