탐욕법 (greedy method)

알고리즘 스터디

탐욕법

10.1 도입

탐욕법(greed method)은 가장 직관적인 알고리즘 설계 패러다임 중 하나

• 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.
• 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못한다.
• 따라서 탐욕적 알고리즘이 사용되는 경우는 크게 다음 두 가지 로 제한된다. 
  
  1. 탐욕법을 사용해도 할살 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
  2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해를 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있다.

예제 : 회의실 예약

• 회사에 회의실이 하나 밖에 없는데, n(<=100)개의 팀이 각각 회의하고 싶은 시간을 그림 10.1과 같이 제출했다고 할때, 이 중 서로 겹치지 않는 회의들만을 골라서 진행해야 한다. 최대 몇개나 선택할 수 있을까?

무식하게 풀 수 있을까?

• 이 문제를 무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겹치지 않는 답들을 걸러내고 그중 가장 큰 부분 집합을 찾아낸다.
• 그러나 집합의 크기가 n일 때 부분 집합의 수는 2^n이기 때문에 n이 30만 되어도 시간 안에 문제를 풀기는 힘들다.

탐욕적 알고리즘의 구상

• 이 문제를 해결하는 탐욕적인 방법은 길이와 상관 없이 가장 먼저 끝나는 회의부터 선택하는 것이다. 
  
  1. 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 S(min)을 선택한다.
  2. S(min)과 겹치는 회의를 S에서 모두 지운다.
  3. S가 텅 빌 때까지 반복한다.

정당성의 증명 1 : 탐욕적 선택 속성

• 탐욕적 알고리즘의 정당성 증명은 많은 경우 일정한 패턴을 가진다.
• 우리가 처음으로 증명해야할 속성은 동적 계획 법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다. -> 탐욕적 선택속성(greed choice property)
• 앞서 제한 한 알고리즘의 경우, 탐욕적 선택 속성이 성립한다는 말은 다음 조건이 성립한다는 의미이다.

가장 종료 시간이 빠른 회의 S(min)를 포함하는 최적해가 만드시 존재한다.

정당성의 증명 2 : 최적 부분 구조

• 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있을음 보여야 한다.
• 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야한다.

구현

• 전체 시간 복잡도 O(n^2)

코드 10.1 회의실 예약 문제를 해결하는 탐욕적 알고리즘

// 각 회의는 [begin, end] 구간 동안 회의실을 사용한다.
int n;
int begin[100], end[100];
int schedule(){
    // 일찍 끝나는 순서대로 정렬한다.
    vector<pair<int,int>> order;
    for(int i=0; i<n; ++i)
        order.push_back(make_pair(end[i], begin[i]));
    sort(order.begin(), order.end());
    //earliest : 다음 회의가 시작할 수 있는 가장 빠른 시간.
    //selected : 지금까지 선택한 회의의 수
    int earliest = 0, selected = 0;
    for(int i=0; i<order.size()l ++i){
        int meetingBegin = order[i].second, meetingEnd = order[i].first;
        if(earlist <= meetingBegin){
            //earlist 를 마지막 회의가 끝난 시간 이후로 갱신한다.
            elarlist = meetingEnd;
            ++selected;
        }
    }
    return selected;
}

• 위 알고리즘은 O(nlogn) 시간이 걸리는 정렬 후에 선형 시간만이 걸리는 선택 과정을 통해 최적해를 찾아낸다.

난 동적 계획법으로 풀었는데?

schedule(idx) = meeting[idx] 혹은 그 이전에 끝나는 회의들 중 선택할 수 있는 최대 회의 수

• schedule()은 매 단계에서 meeting[idx] 를 선택할지 여부를 결정한다. idx번 회의가 시작하기 전에 끝나는 회의들 중 마지막 회의의 번호를 before[idx] 에 저장했다고 하면 선택하지 않은 경우의 최적해는 schedule(idx-1)로, 선택할 경우의 답은 1+schedule(before[idx])로 재귀적으로 표현할 수 있다.
• before[]를 만드는 데 O(nlogn)의 시간이 걸리고, schedule()의 수행에는 2O(n)의 시간이 걸리니 사실 탐욕법과 다를 것이 없다.
• 많은 경우 동적 계획법이 아니라 탐욕법을 사용하는 이유는 동적 계획법이 필요한 메모리나 시간이 과도하게 크기 때문이다.

예제 : 출전 순서 정하기

경기	1	2	3	4	5	6
러시아팀	3,000	2,700	2,800	2,200	2,500	1,900
한국팀	2,800	2,750	2,995	1,800	2,600	2,000

- 어느순서대로 선수들을 내보내야 승수를 최대화 할 수 있을까?

무식하게 풀 수 있을까?

• 이 문제에는 n!개의 답이 있어서 n이 조금만 커져도 답의 개수가 너무 많아서 시간안에 다 셀 수 없다.

그렇다면 동적 계획법은 어떨까?

order(taken) = 각 한국 팀 선수를 이미 순서에 추가 했는지 여부가 taken에 주어질 때, 남은 선수들의 적절히 배치해서 얻을 수 있는 최대 승수

• 시간복잡도 O(n^2) -> 그래도 느리다.

탐욕적 알고리즘의 구상

• 맨 앞 경기부터 한 명씩 출전할 한국 선수를 정한다. 상대방 선수를 이길 수 있는(레이팅이 같거나 높은) 한국 선수가 있는 경우 그중 레이팅이 가장 낮은 선수를 상대방 선수와 경기시킨다. 만약 상대방 선수가 한국팀의 모든 선수보다 레이팅이 높다면 남은 선수 중 가장 레이팅이 낮은 선수와 경기시킨다.

탐욕적 선택 속성 증명

항상 우리가 하는 선택을 포함하는 최적해가 존재한다는 걸 증명한다.

1) 질 수 밖에 없는 경기 (A: 가장 레이팅이 낮은 선수)

러시아	…	999,999,999	…	x	…	1,900
한국	…	B	…	A	…	2,000

-> A,B 를 바꿔도 승수가 줄어드는 일이 없다,

2) 이길 수 밖에 없는 경기(A:가장 레이팅이 낮은 선수)

러시아	…	2,000	…	x	…	1,900
한국	…	B	…	A	…	2,000

-> A, B를 바꿔서 승리할 경우 원래 순서 또한 최적해임

두 경우 모두 우리의 선택은 최다 승을 보장함

최적 부분 구조 증명

• 첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들의 경기에 배정하는 부분 문제를 얻을 수 있다. 이때 남은 경기에서도 당연히 최다승을 얻는 것이 좋으니 최적 부분 구조도 자명하게 성립한다.

구현

코드 10.2 출전 순서 정하기 문제를 해결하는 탐욕적 알고리즘

int order(const vector<int>& russion,
          const vector<int> &korean){
    int n = russion.size(), wins = 0;
    // 아직 남아 있는 선수들의 레이팅
    multiset<int> ratings(korean.begin(), korean.end());
    for(int rus=0;rus<n;rus++){
        // 가장 레이팅이 높은 한국 선수가 이길 수 없는 경우
        // 가장 레이팅이 낮은 선수와 경기 시킨다.
        if(*ratings.rbegin() < russian[rus])
            ratings.erase(ratings.begin());
        else{
            ratings.erase(ratings.lower_bound(russian[rus]));
            ++wins;
        }
    }
return wins;
}   

탐욕적 알고리즘 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어보는 것이 효율적이다.
3. 어떤 방식이 동작할 것 같으면 두 가지의 속성을 증명해본다. 
   a. 탐욕적 선택 속성 
   b. 최적 부분 구조

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