[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java)
그리디 알고리즘
그리디 알고리즘은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 이는 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다. 그러나 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다는 것이다.
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있다. 이럴 때 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰인다.
그리디 알고리즘은 주로 코테나 대회에서는 첫 번째 용도로만 사용된다. 근사해를 찾는 문제는 대게 출제되지 않을 뿐더러, 가끔 근사해를 구하는 문제가 주어졌다 해도 탐욕적 알고리즘보다 조합 탐색이나 *메타휴리스틱 알고리즘들이 더 좋은 답을 주는 경우가 많기 때문이다.
*메타휴리스틱 알고리즘이란 최적화 알고리즘의 한 종류로, 일반 최적화 알고리즘은 목적 함수를 미분할 수 있다는 가정을 사용하는 반면, 메타휴리스틱은 이런 가정을 하지 않기 때문에 대회에서 종종 사용된다.
탐욕법의 개념은 간단하다. 하지만 많은 사람들의 발목을 잡는 주제 중 하나이기도 하다. 한 문제를 탐욕적으로 해결하는 방법이 한 가지만 있는 것이 아닌 경우도 많은데, 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기가 어렵기 때문이다. 실제로 최적해를 얻을 수 있는 접근이 직관적이지 않기 때문에 실수에 유의해야 한다. 그러니 그리디 알고리즘 연습 문제를 풀 때는 알고리즘의 정당성을 증명하는 과정을 빼먹지 않고 연습하는 것이 좋다.
그리디 알고리즘 정당성 증명
탐욕적 알고리즘의 정당성 증명은 많은 경우 일정한 패턴을 가진다. 이 증명 패턴은 탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 두 가지의 속성을 증명함으로써 보인다.
- 탐욕적 선택 속성 (greedy choice property)
- 최적 부분 구조 (optimal substructure)
설명하기 쉽게 탐욕법이 유용하게 사용되는 문제 중 유명한 예로 활동 선택 문제(activity selection problem)인 회의실 예약을 예로 들어보자. 백준 1931번 회의실 배정과 같은 유형의 문제이므로 해당 문제를 풀이해도 된다.
회의실 예약 - 활동 선택 문제(activity selection problem)
회사에 회의실이 하나밖에 없는데, n(<=100)개의 팀이 각각 회의하고 싶은 시간을 다음과 같이 제출했다고 하자. 두 팀이 회의실을 같이 쓸 수 없기 때문에 이 중 서로 겹치지 않는 회의들만을 골라내서 진행해야 한다. 최대 몇 개나 선택할 수 있을까?
해당 문제의 답은 여러 방법이 존재할 수 있다. 서로 겹치지 않은 회의들의 집합은 모두 이 문제의 답이라고 할 수 있다. 이때 우리가 원하는 가장 좋은 답, 곧 최적해는 크기가 가장 큰 부분 집합이다.
무식하게 풀기?
무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겹치지 않는 답들을 걸러내고 가장 큰 부분 집합을 찾아낸다. 그러나 집합의 크기가 n일 때 부분 집합의 수는 2^n이기 때문에 n이 30만 되어도 10억정도가 넘게 되어 시간 안에 풀기 힘들다.
탐욕적 알고리즘 구상
이런 문제를 '탐욕적으로' 해결하는 방법을 몇 가지 떠올릴 수 있다.
- 길이가 짧은 회의부터 하나하나 순회하면서 앞의 것들과 겹치지 않는 것들을 추가하기
- 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하기
첫 번째 방법은 그럴듯해 보이지만 짧은 회의가 긴 회의 두 개 사이에 위치하게 된다면 해당 방법은 최적해에 속하지 않으므로 사용하기 부적절하다.
그래서 두 번째 방법을 선택해야 한다. 가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치는 것들을 모두 지운 뒤 다시 이 중에서 먼저 끝나는 회의를 선택하기를 반복하는 것이다.
- 목록 S에 남은 회의 중 가장 일찍 끝나는 회의 S_min을 선택한다.
- S_min과 겹치는 회의를 S에서 모두 지운다.
- S가 텅 빌 때까지 반복한다.
탐욕적 알고리즘 방식을 선택하였으니 이제 해당 방법이 항상 최적해를 찾아낼 수 있다는 정당성을 두 가지 속성을 통해 증명해주면 된다.
1. 탐욕적 선택 속성 (greedy choice property)
처음으로 증명해야 할 속성은 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다. 이 속성은 매우 중요하기 때문에 따로 이름을 붙여 탐욕적 선택 속성이라고 부른다.
어떤 알고리즘에 이 속성이 성립할 경우, 우리가 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나이다. 따라서 탐욕적인 선택을 해서 '손해'를 볼 일이 없다는 것을 알 수 있다. 따라서 앞에서 제안한 알고리즘의 경우, 탐탐욕적 선택 속성이 성립한다는 말은 다음 조건이 성립한다는 의미이다.
- 가장 종료 시간이 빠른 회의(S_min)를 포함하는 최적해가 반드시 존재한다.
증명
S의 최적해 중에 S_min을 포함하지 않는 답이 있다고 가정하자. 이 답은 서로 겹치지 않은 회의의 목록으로 첫 번째로 개최되는 회의를 지우고 S_min을 대신 추가해서 새로운 목록을 만들자.
해당 그림은 위의 예제에 속하는 S_min을 포함하지 않는 최적해 중 하나이다.
S_min은 S에서 가장 일찍 끝나는 회의이기 때문에(혹은 가장 일찍 끝나는 회의 중 하나) 지워진 회의는 S_min보다 일찍 끝날 수는 없다. 따라서, 해당 최적해에서 첫 번째로 개최되는 회의를 지우고 S_min을 추가하면 다음과 같이 된다.
→ 따라서 두 번째 회의와 S_min을 겹치는 일은 없으며, 새로 만든 목록도 최적해 중 하나가 된다.
→ 따라서 항상 S_min을 포함하는 최적해가 존재한다. 이와 같은 증명은 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음을 나타낸다.
2. 최적 부분 구조 (optimal substructure)
이렇게 탐욕적인 방법으로 선택하는 것이 항상 최적의 답을 줄 수 있다고 해서 증명이 끝난 것은 아니다. 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 보여야 한다. 당연하지만 경우에 따라 성립하지 않은 경우도 있기 때문이다. 최적 부분 구조는 DP에서 다루듯이 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여주면 된다.
다행히 이 속성은 대게 매우 자명해서 따로 증명할 필요가 없는 경우가 대부분이다. 첫 번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에 당연히 최대한 많은 회의를 선택하게 되므로 최적 부분 구조가 성립함을 알 수 있다.
구현
위의 알고리즘을 그대로 구현하면 O(n^2)이 되어 시간이 오래 걸린다. 빠르게 구현하는 한 방법은 처음에 모든 회의를 종료 시간의 오름차순으로 정렬해 두는 것이다.
그러면 탐색 과정은 정렬된 배열의 첫 번째 회의는 무조건 선택해도 된다. 그 후 겹치는 회의와 겹치지 않는 회의를 찾으면서 회의들은 오름차순으로 정렬되어 있기 때문에, 겹치지 않는 회의를 찾자마자 나머지를 보지 않고 선택해도 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Meeting implements Comparable<Meeting>{
int start;
int end;
public Meeting(int start, int end) {
this.start =start;
this.end = end;
}
@Override
public int compareTo(Meeting o) {
if(this.end>o.end) return 1;
else if(this.end<o.end) return -1;
else return this.start-o.start;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Meeting> list = new ArrayList<>();
StringTokenizer st = null;
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.add(new Meeting(a,b));
}
Collections.sort(list);
int endTime=0, cnt=0;
for(Meeting m : list) {
if(endTime<=m.start) {
endTime = m.end;
cnt++;
}
}
System.out.println(cnt);
}
}
참고