탐욕법에 대해서, 회의실 예약 문제

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

탐욕법

문제를 여러 조각으로 쪼개고, 각 조각으로 답의 일부를 작성하는 것은 다른 알고리즘과 같다. 핵심은 각 조각을 해결할 때 눈 앞의 가장 좋은 방법을 선택하는 것이다. 즉, 지금 하는 선택이 남은 선택에 끼칠 영향을 고려하지 않는다.

 

탐욕법을 통해 최적해를 구할 수 있다면 동적 계획보다 빠르지만, 최적해를 찾지 못 하는 경우가 많다. 따라서, 탐욕법을 사용할 정당성을 증명하는 과정이 필요하다.

탐욕적으로 해결하는 순서

전체 문제를 여러 조각으로 나누고 각 조각을 해결함에 있어서 탐욕적인 선택이 무엇일지 생각해본다. 예제 입력 몇 개를 손으로 풀어보면 직관을 얻을 수도 있다. 동작할 것 같은 방법이 생각나면 다음 속성들을 증명해봐야 한다. 

 

먼저, 문제가 탐욕적 선택 속성을 가지는지 확인한다. 각 단계에서 탐욕적으로 선택한 답을 포함하는 최적해가 존재함을 보이면 되는데, 보통 우리가 선택한 답과 다른 최적해의 존재를 가정하고, 이를 우리가 선택한 답을 포함하는 것으로 바꿨을 때 손해를 보지 않음을 보이면 된다.

 

다음으로 문제가 최적 부분 구조를 가짐을 증명한다. 각 단계에서 최적의 선택이 전체 최적해로 이어지는지를 증명한다. 이를 통해 각 문제의 탐욕적 선택이 전체 문제의 최적해로 이어짐을 알 수 있다. 많은 경우에 최적 부분 구조를 가지는 문제인지 직관적으로 알 수 있다. 

회의실 예약(링크)

탐욕적으로 생각해보자. 매번 목록에 남은 회의 중 가장 빨리 끝나는 회의를 선택하고 이를 목록이서 지운다. 목록이 빌 때까지 이 과정을 반복한다.

 

탐욕적인 방법을 고안했으므로 정당성을 증명해보자. 이 문제는 탐욕적으로만 선택해도 최적해를 구할 수 있는가? 그렇다. 즉, 탐욕적으로 골라도 '손해' 보지 않는다.

 

가장 먼저 끝나는 회의를 선택하지 않은 최적해가 있다고 하자. 이 최적해는 서로 겹치지 않는 회의 목록이다. 여기서 첫 번째로 개최된 회의 대신 가장 빨리 끝나는 회의를 선택한다고 하면 원래의 회의보다 짧은 회의를 선택하므로 목록의 회의 개수는 변하지 않는다.

 

즉, 가장 빨리 끝나는 회의를 선택하는 방법 (탐욕적 선택) 을 사용해도 손해보지 않는다.

 

이 문제는 최적 부분 구조를 가지는가? 이 문제에서 부분 문제의 최적해는 전체 문제의 최적해이다. 직관적으로 생각했을 때 당연히 최대한 많은 회의를 골라야 한다. 즉, 어떤 단계까지든 고른 회의는 항상 최대한 많이 골라야 한다. 

 

각 문제를 해결함에 있어 탐욕적인 선택을 해도 손해보지 않고 그렇게 선택한 최적해가 전체 문제의 최적해가 되므로 이 문제는 매번 탐욕적인 선택을 통해 해결할 수 있다.

C++ 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int begin[100], end[100];

int schedule() {
    // Sort by fastest ending
    vector<pair<int, int>> order;
    for (int i = 0; i < n; ++i) 
        order.push_back(make_pair(end[i], begin[i]));
    // sort without compare function compares with first element in pair
    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;

        // Ignore meetings start before current meeting ends
        if (earliest <= meetingBegin) {
            earliest = meetingEnd;
            ++selected;
        }
    }

    return selected;
}