탐욕법(Greedy)

탐욕법이란?

• 원하는 답을 재귀 호출처럼 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어감
• 모든 선택지 중 가장 좋은 답을 찾는 완전탐색/동적 계획법과 달리 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택
• 즉, 탐욕법은 지금의 선택이 앞으로 남은 선택에 어떤 영향을 미칠지 고려하지 않음
• 탐욕 알고리즘을 이용할 경우 알고리즘의 정당성을 증명하는 과정이 필요함

탐욕법이 적용되는 사례

• 탐욕법을 사용해도 항상 최적해를 구할 수 있을 경우 (동적 계획법보다 수행시간이 훨씬 빠름)
• 시간/공간적 제약으로 인해 다른 방법으로는 최적해를 찾기 어려울 경우(최적해 대신 근사해 찾는 것으로 타협)

[예제] 회의실 예약

회사에 회의실이 하나밖에 없는데, n개의 팀이 각각 회의하고 싶은 시간을 제출했다. 두 팀이 회의실을 같이 사용할 수는 없기 때문에 이 중 서로 겹치치 않는 회의들만을 골라 진행해야 할 때, 최대 몇 개의 회의를 선택할 수 있을까?

 

풀이 방법

1. 무식하게 풀기 : 모든 부분 집합을 하나하나 만들어보며 그 중 회의들이 겹치지 않는 답을 걸러내고, 그 중에서 가장 큰 부분 집합을 찾아냄 -> 집합의 크기가 커질 수록 시간이 지수배로 증가하므로 시간 안에 문제를 풀기 힘듬

2. 탐욕법1 : 길이가 가장 짧은 회의부터 순회하며 앞의 것들과 겹치치 않는 것들을 추가함 -> 아래의 사진과 같을 경우 긴 회의 두개 대신 짧은 회의 하나만을 선택함

3. 탐욕법2 : 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하고, 해당 회의와 겹치는 것들은 모두 지운 뒤 다시 이중에서 가장 먼저 끝나는 회의 선택 -> 최적해

• 목록 S의 회의 중 가장 일찍 끝나는 회의 Smin 선택
• Smin과 겹치는 회의는 S에서 지움
• S가 모두 빌 때까지 위의 두 과정 반복

탐욕법 정당성의 증명

1. 탐욕적 선택 속성 : 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것 증명
   -> 위의 회의실 예제에 적용해보면, 가장 종료시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다는 것을 증명하면 됨. 
   -> 증명 ) S의 최적해 중에 Smin을 포함하지 않는 답이 있다고 가정하고, 해당 목록에서 첫번째로 개최되는 회의를 지우고 Smin을 추가해서 새로운 목록을 만들어 보자. Smin은 S에서 가장 일찍 끝나는 회의이기 때문에 지워진 회의는 Smin보다 일찍 끝날 수 없다. 따라서 두번째 회의와 Smin은 겹치는 일이 없으며, 새로 만든 목록도 최적해가 된다! 즉, Smin을 포함하는 최적해는 항상 존재한다.
2. 최적 부분 구조 : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 함. (해당 속성은 보통 매우 자명해서 따로 증명할 필요 없음)
   -> 위의 회의실 예제에 적용해보면, 첫 번째 회의를 제대로 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에서는 당연히 최대한 많은 회의를 선택해야함!

회의실 예약 예제 구현

• 모든 회의의 목록을 저장해두고, 한 회의를 선택할 때마다 겹치는 회의들을 모두 제거하는 방법을 사용할 경우, 시간 복잡도가 O(n^2)가 됨
• 처음에 모든 회의를 종료시간의 오름차순으로 정렬(quick sort)해 두고(O(nlogn)), 이후 겹치는 회의를 지울 필요 없이, 정렬된 배열을 순회하면서 첫 번째 회의와 겹치지 않는 회의를 찾고, 계속 같은 방법으로 실행할 경우(O(n)) 쉽고 빠르게 구현 가능

예제 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int beginTime[100], endTime[100];
int schedule() {
	// 일찍 끝나는 순으로 정렬
	vector<pair<int, int>> order;
	for (int i = 0; i < n; i++)
		order.push_back(make_pair(beginTime[i], endTime[i]));
	sort(order.begin(), order.end());
	// earlist : 다음 회의가 시작할 수 있는 가장 빠른 시간
	// selected : 지금까지 선택한 회의 수
	int earliest = 0, selected = 0;
	for (int i = 0; i < order.size(); i++) {
		int meetingBegin = order[i].second, meetingEnd = order[i].first;
		if (earliest <= meetingBegin) {
			earliest = meetingEnd;
			++selected;
		}
	}
	return selected;
}

 

 

 

출처 : 알고리즘 문제해결전략