종만북 10장 탐욕법
이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
➖ 21-07-26
도입
-
탐욕법(greedy method): 모든 선택지를 고려해보고 그중 전체 답이 가장 좋은 것을 찾는 완전 탐색/동적 계획법과 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다
-
탐욕법 알고리즘을 사용하는 경우
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려워, 최적해 대신 적당히 괜찮은 답(근사해)를 찾는 것으로 타협하는 경우
- 한 문제를 탐욕적으로 해결하는 방법이 여러가지인 경우가 많다
-> 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지 알아내기 어렵다
-> 알고리즘의 정당성을 증명하는 과정 필요
회의실 예약 문제
-
활동 선택 문제(activity selection problem)
-
회사에 회의실이 하나밖에 없다
n(<= 100)개의 팀이 각각 회의하고 싶은 시간을 제출하고이 중 서로 겹치지 않는 회의들을 골라서 진행해야 한다
최대 몇 개의 회의를 선택할 수 있을까? -
무식하게 푸는 방법:
모든 부분 집합을 하나하나 만들어 보며 회의들이 겹치지 않는 답들을 구하고 그 중 가장 큰 부분 집합을 찾아낸다
-> 집합의 크기 n일 때 부분 집합의 수 2^n
-> 시간 안에 풀기 힘들다
탐욕적으로 푸는 방법
-
길이와 상관 없이 가장 먼저 끝나는 회의부터 선택
가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치는 것을 모두 지운 뒤 다시 이중에서 가장 먼저 끝나는 회의를 선택하기를 반복한다 -
탐욕적 알고리즘의 형태
- 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 smin
- smin과 겹치는 회의를 S에서 모두 지운다
- S가 텅 빌 때까지 반복한다
정당성의 증명
- 탐욕적 알고리즘의 정당성 증명은 두 가지의 속성을 증명함으로써 보인다
- 탐욕법 선택 속성(greedy choice property)
-
동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있음을 증명해야 한다
-> 어떤 알고리즘이 이 속성이 성립할 경우, 우리가 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나이다 -
앞서 제안한 알고리즘의 경우, 탐욕적 속성이 성립한다는 말은
가장 종료시간이 빠른 회의(smin)를 포함하는 최적해가 반드시 존재한다
는 조건이 성립한다는 것을 말한다 -
S의 최적해 중에 smin을 포함하지 않는 답이 있다고 하자
이 목록에서 첫 번째로 개최되는 회의를 지우고 smin을 대신 추가해서 새로운 목록을 만든다
smin은 가장 일찍 끝나는 회의이기 때문에 지워진 회의가 smin보다 일찍 끝날 수는 없다
따라서 두번째 회의와 smin이 겹치는 일은 없으며 새로 만든 목록도 최적해 중 하나가 된다
-> 우리가 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없다
- 최적 부분 구조(optimal substructure)
-
동적 계획법을 다룰 때 했듯이, 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 한다
-
이 속성은 대개 매우 자명해서 대부분 따로 증명할 필요가 없다
구현
- 처음에 모든 회의를 종료 시간의 오름차순으로 정렬해두면 쉽고 빠르게 구현할 수 있다
//각 회의는 [begin, end) 구간동안 회의실을 사용한다
int n;
int begin[100], end[100];
int schedule(){
//일찍 끝나는 순서대로 정렬
//이때, sort()함수는 pair의 first를 기준으로 정렬하므로
//(end, begin)의 형태로 pair를 만들어 저장한다
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(); ++i){
int meetingBegin = order[i].second;
int meetingEnd = order[i].first;
if(earliest <= meetingBegin){
earliest = meetingEnd;
++selected;
}
}
return selected;
}- 탐욕법으로 최적해를 구할 수 있는 많은 문제들을 동적 계획법으로도 풀 수 있다
-> 그러나 많은 경우 동적 계획법이 아닌 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리 / 시간이 과도하게 크기 때문이다
출전 순서 구하기 (MATCHORDER)
-
각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 된다
1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정한다
상대방 팀 선수들의 순서를 알고 있을 때, 어느 순서대로 선수들을 내보내야 승수를 최대화할 수 있을까? -
무식하게 푸는 방법:
n명의 선수들이 있을 때 선수들을 내보내는 순서는 n!가지
-> 시간 안에 풀기 힘들다 -
동적 계획법으로 푸는 방법:
한국팀의 출전 순서를 맨 앞에서부터 한 명씩 정해가기로 하면, 각 선수를 지금까지 순서에 추가했는지를 나타내는 불린값 배열만을 받는 부분 문제를 만들 수 있다
-> order(taken) = 각 한국팀 선수를 이미 순서에 추가했는지의 여부가 taken에 주어질 때, 남은 선수들을 적절히 배치해서 얻을 수 있는 최대 점수
-> 시간 복잡도 O(n * 2^n)
탐욕적으로 푸는 방법
-
각 팀이 100명의 선수들로 구성되어있다면 동적 계획법보다 더 빠른 알고리즘을 만들어야 한다
-> 이렇게 막막할 때 탐욕적 알고리즘을 한 번쯤 떠올려 볼 만 하다
-> 탐욕적 알고리즘을 설계하는 좋은 방법은 간단한 입력 몇 개를 손으로 풀어 보면서 패턴을 찾는 것이다 -
맨 앞 경기부터 한 명씩 출전할 한국 선수를 정한다
-> 상대방 선수를 이길 수 있는 한국 선수가 있는 경우: 그중 레이팅이 가장 낮은 선수를 상대방 선수와 경기시킨다
-> 상대방 성수를 이길 수 있는 한국 선수가 없는 경우: 남은 선수 중 가장 레이팅이 낮은 선수와 경기시킨다
정당성 증명
- 탐욕법 선택 속성(greedy choice property)
-
1:1 경기를 질 수밖에 없는 경우:
이 경기에 가장 레이팅이 낮은 선수 A대신 선수 B를 내보내는 최적해가 있다고 가정한다
-> 최적해에서 A와 B의 순서를 바꾸게 되면 이번 경기는 어차피 질테지만, A를 상대했던 선수는 A보다 레이팅이 더 높은 B와 상대하게 된다
-> 따라서 승수가 더 줄어들 일은 없다 -
1:1 경기를 이길 수 있는 경우 (1):
이 경기에 승리할 수 있는 선수 중 레이팅이 가장 낮은 A대신 레이팅이 더 높은 B를 내보내는 최적해사 있다고 가정한다
-> 최적해에서 A와 B의 순서를 바꾸게 되면 이번 경기는 어차피 승리할테고, A를 상대했던 선수는 A보다 레이팅이 더 높은 B와 상대하게 된다
-> 따라서 승수가 더 줄어들 일은 없다 -
1:1 경기를 이길 수 있는 경우 (2):
이 경기에 승리할 수 있는 선수 중 레이팅이 가장 낮은 A대신 레이팅이 더 낮은 C를 내보내는 최적해사 있다고 가정한다
그렇다면 이 경기는 이길 수 있지만 지게 된다
-> 최적해에서 A와 C의 순서를 바꾸게 되면 A가 했던 경기는 C가 해서 질 수도 있겠지만, 이 경기는 승리로 바뀐다
-> 승수가 1늘고 1줄었으니 승수가 더 줄어들 일은 없다 -
탐욕적 속성을 증명하는 패턴:
항상 우리가 선택한 방법을 포함하는 최적해가 있음을 증명하기 위해, 우선 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정하고 이것을 적절히 조작하여 우리가 선택한 방법을 포함하는 최적해를 만들어낸다
- 최적 부분 구조(optimal substructure)
- 첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들을 경기에 배정하는 부분 문제를 얻을 수 있다
-> 이때 남은 경기에서도 최다승을 얻는 것이 당연히 좋으니 최적 부분 구조가 자명하게 성립한다
구현
- 아직 출전하지 않은 선수들의 레이팅을 이진 검색 트리인 multiset< int > 에 저장
-> 이길 수 있는 가장 레이팅이 낮은 선수 탐색 O(lgn)
-> 선택한 선수의 레이팅 삭제 O(lgn)
int order(const vector<int>& russian, const vector<int>& korean){
int n = russian.size();
int wins = 0;
//아직 남아있는 선수들의 레이팅 오름차순으로 정렬하며 저장
//두 개의 iterator 사이에 있는 원소들로 초기화된다
multiset<int> ratings(korean.begin(), korean.end());
for(int rus = 0; rus < n; ++rus){
//ratings.rbegin(): ratings의 가장 마지막 원소 = 가장 높은 레이팅
//ratings.begin(): ratings의 가장 첫 번째 원소 = 가장 낮은 레이팅
//가장 레이팅이 높은 한국 선수가 이길 수 없는 경우
//가장 레이팅이 낮은 선수와 경기시킨다
if(russian[rus] > *ratings.rbegin())
ratings.erase(ratings.begin());
//이외의 경우 이길 수 있는 선수 중 가장 레이팅이 작은 선수와 경기시킨다
else{
//lower_bound: key값의 위치 반환
//key값이 없으면 key값을 초과하는 가장 첫 번째 원소의 위치반환
ratings.erase(lowerbound(russian[rus]));
++wins;
}
}
return wins;
}탐욕적 알고리즘 레시피
-
문제의 답을 만드는 과정을 여러 조각으로 나눈다
-
각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다
-> 직관을 얻기 위해 작은 입력 몇 개를 직접 손으로 직접 풀어본다 -
어떤 방식이 동작할 것 같으면 두 가지 속성을 증명해본다
-> 탐욕적 선택 속성: 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 증명
-> 최적 부분 구조: 각 단계에서 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부 증명
도시락 데우기 (LUNCHBOX)
-
n 개의 도시락이 있다. i 번째 도시락을 데우는 데 m_i 초가 걸리고 먹는 데 e_i초가 걸린다
도시락을 나누어 데울 수 없고, 각 사람은 자기 도시락을 다 데우는 대로 곧장 먹기 시작한다
점심을 먹는 데 걸리는 시간은 첫 번째 도시락을 데우기 시작할 때부터 모든 사람이 도시락을 다 먹을 때까지 걸리는 시간이다
점심시간을 마칠 수 있는 최소 시간은? -
i 번째 도시락을 먹을 때까지 걸리는 시간: 0 ~ i 번째까지의 도시락을 데우는 시간의 합 + i 번째 도시락을 먹는데 걸리는 시간
-
점심시간을 마치는 시간 = 0 ~ n-1 번째 도시락 중 먹을 때까지 걸리는 시간이 가장 오래걸리는 도시락을 다 먹은 시간
탐욕적으로 푸는 방법
-
모든 도시락을 먹는 데 같은 시간 C가 걸린다고 가정하면
점심시간을 마치는 시간 = 모든 도시락을 데우는 시간의 합 + C
-> 점심 시간을 마치는 시간은 도시락을 데우는 시간과는 관련이 없이 먹는 시간과 관련 있다 -
탐욕적으로 푸는 방법: 도시락을 먹는 데 오래 걸리는 도시락부터 데우는 것
정당성 증명
- 탐욕법 선택 속성(greedy choice property)
- 먹는데 가장 오래 걸리는 도시락 A를 x 번째에 데우고, 덜 오래걸리는 도시락 B를 제일 먼저 데우는 최적해가 존재한다고 가정한다
(1) 첫 번째 도시락을 먹는 사람이 식사가 끝나는 시간
= B 도시락을 데우는 시간의 합 + 도시락 B를 먹는 시간
(2) x 번째 도시락을 먹는 사람이 식사가 끝나는 시간
= 첫 번째 ~ x 번째까지의 도시락을 데우는 시간의 합 + 도시락 A를 먹는 시간
- 최적해에서 도시락 A와 도시락 B를 데우는 순서를 바꾸게 되면
(3) 첫 번째 도시락을 먹는 사람이 식사가 끝나는 시간
= A 도시락을 데우는 시간의 합 + 도시락 A를 먹는 시간
(4) x 번째 도시락을 먹는 사람이 식사가 끝나는 시간
= 첫 번째 ~ x 번째까지의 도시락을 데우는 시간의 합 + 도시락 B를 먹는 시간
-> (3) < (2) , (4) < (2) 이므로 최적해에서 식사를 마치는 시간보다 더 오래 걸릴 수 없다
- 최적 부분 구조(optimal substructure)
- 첫 번쨰 도시락을 정하고 나면 나머지 도시락을 배치하는 부분 문제를 얻을 수 있다
-> 이때 나머지 도시락을 다 먹기까지 시작을 최소회하는 것이 당연히 좋으니 최적 부분 구조가 자명하게 성립한다
구현
- pair< int, int >를 사용하여 도시락을 먹는 데 걸리는 시간과 도시락을 데우는 데 걸리는 시간 저장
-> 도시락을 먹는 데 걸리는 시간의 역순으로 정렬해야 한다
-> e[i]의 부호를 뒤집어 넣음으로써 역순 정렬을 더 간단하게 구현함
int n, e[MAX_N], m[MAX_N];
int heat(){
//어느 순서로 데워야 할지를 정한다
vector<pair<int><int>> order;
for(int i = 0; i<n; ++i)
order.push_back(make_pair(-e[i], m[i]));
sort(order.begin(), order.end());
//해당 순서대로 데워먹는 과정 시뮬레이션
int ret = 0, beginEat = 0;
for(int i = 0; i<n; ++i){
//먹기 시작하는 시간 = 지금까지의 모든 도시락을 데우는 데 걸린 시간의 합
beginEat += order[i].second;
//먹는 데 걸리는 시간의 부호를 뒤집어 저장했기 때문에 - 연산
ret = max(ret, beginEat -order[i].first);
}
return ret;
}