알고리즘 문제 해결 전략 1권 10.탐욕법

10.1 도입

원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 그 중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택함. 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않습니다. 

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만날 경우, 동적 계획법보다 수행 시간이 훨씬 빠름

2. 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답을 찾는 것으로 타협할 수 있음

 

가끔 근사해를 구하는 문제가 주어졌다 해도 탐욕적 알고리즘보다 11장에서 다루는 조합 탐색이나 메타휴리스틱 알고리즘들이 더 좋은 답을 주는 경우가 많음. 탐욕적 알고리즘 연습 문제를 풀 때는 알고리즘의 정당성을 증명하는 과정을 빼먹지 않고 연습하는 것이 좋음

 

예제 문제 : 회의실 예약

집합의 크기가 N일 때 부분 집합의 수는 2^N이기 때문에 N이 30만이 되어도 시간 안에 문제를 풀기는 힘듭니다.

탐욕법을 사용하는 알고리즘들은 꼭 그럴듯 하다고 해서 장답을 내는 것이 아닙니다. 

1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의를 선택함

2. Smin과 겹치는 회의를 S에서 모두 지운다

3. S가 텅 빌 때까지 반복한다

 

탐욕적 선택 속성. 이 속성이 성립할 경우, 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나임. 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재함. 이와 같은 증명은 우리가 가장 일찍 끝나는 회의를 서낵해서 최적해를 얻는 것이 불가능해지는 경우는 없음을 보여줌

 

최적 부분 구조. 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 함. 첫 번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에 당연히 최대한 많은 회의를 선택해야 함.

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int n;
int arrBegin[100], arrEnd[100];
int schedule() {
	vector<pair<int, int>> order;
	for (int i = 0; i < n; i++) {
		order.push_back(make_pair(arrEnd[i], arrBegin[i]));
	}
	sort(order.begin(), order.end());
	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;
}

탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있습니다. 탐욕법으로 최적해를 찾을 수 있다는 말은 지금 한 단계만을 고려해도 답을 찾을 수 있다는 의미입니다. 모든 단계를 고려하는 동적 계획법이 답이 틀릴 리가 없음.