2019. 6. 3. 18:50ㆍ알고리즘/그리디
그리디 알고리즘
그리디 알고리즘이란 눈앞의 이익만 우선 추구하는 알고리즘을 말한다.
예를들어 이진 트리에서 그리디 탐색을 한다고 했을때 트리의 내용을 사전에 알지 못하는 상태에서
루트부터 시작해 왼쪽으로 갈지 오른쪽으로 갈지 매 단계마다 결정해서 가장 큰값을 찾아낸다고 하자
루트의 오른쪽에 60 이 있고 루트의 왼쪽에 15가 있다면 그리디는 눈앞의 이익을 우선하기 때문에 60을 쫒아간다.
하지만 60은 밑에 자식이 없고 15는 밑에 100이라는 자식이 있다면 결국 15로 갔을때 가장 큰값이 나오게된다.
이렇듯 그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우가 있다.
그 예로는 최소 신장 트리를 찾는 프림알고리즘이 있다.
프림 알고리즘은 그래프에서 연결하는 간선 가중치의 합이 가장 작은 것을 찾는 것인데 그리디로 알고리즘을 작성하여도 최적해를 보장하게 된다.
다음은 그리디 알고리즘에 관한 문제들을 준비했다.
활동 선택 문제
활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 겁니다.
아래에서 Si는 시작시간, Fi는 종료시간입니다. 같은 강의실을 사용해야 하므로 A1과 A4는 동시에 선택할 수 없겠죠? A1과 A2도 시간이 겹치므로 선택할 수 없습니다. 그렇지만 A1과 A3는 선택할 수 있죠. 이렇게 선택하여 가장 많은 수업을 할 수 있는 경우를 찾는 겁니다. 복잡하죠?
결과적으로 보면 A1, A3, A6, A8이나 A1, A3, A7, A9 등을 고르면 정답입니다. 문제는 이것을 컴퓨터에게 어떻게 고르도록 시키느냐겠죠.
이 문제는 동적 프로그래밍을 통해서도 풀 수 있습니다. 하나의 예를 들어 G18을 A1이 종료된 후부터, A8이 시작하기 전 활동들의 집합이라고 보면, G18 = {A3, A5, A6, A7}입니다. 이 중에서 최적의 조합(활동들이 겹치지 않고 개수는 최대)을 B18이라고 하면, 하나의 예로 B18 = {A3, A6}라고 할 수 있습니다. {A3, A7}도 되겠네요.
B18에서 A6를 골랐다고 칩시다. A6를 고르면 이제 문제는 두 개로 쪼개집니다. G16과 G68에서 각각 최적인 B16와 B18을 찾는 거죠. 이제 B16과 B18의 개수와 A6 1개를 더하면 최적 활동의 개수를 알 수 있습니다. 이를 식으로 나타내면 C[i,j] = max(C[i,k] + C[k,j] + 1)이 됩니다. C는 집합 Gij의 최적 개수를 나타냅니다. max는 B18에서 A6 말고 다른 것을 골랐을 때의 경우도 모두 생각해서 그 중 최적을 찾는 겁니다.
이렇게 동적 프로그래밍으로 할 수도 있지만, 문제는 이렇게 하면 모든 C들을 구해야한다는 겁니다. 하지만 우리는 그리디 알고리즘으로 더 효율적으로 풀 수 있습니다.
직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 됩니다. 그래야 다른 활동들을 더 많이 선택할 수 있기 때문이죠. 위의 경우에서는 첫 선택으로 가장 빨리 끝나는 A1을 골라야겠죠. A1을 골랐다면 이제 A2와 A4는 고를 수 없습니다(A1이랑 겹침). 그 다음 선택은 다음으로 일찍 끝나는 A3가 될 겁니다. 그 다음은 A6, 마지막은 A8이 되어 최종적으로 {A1, A3, A6, A8}이 됩니다.
코드
package greedy;
import java.util.Arrays;
import java.util.Comparator;
public class knapsack {
public static void main(String[] args) {
Integer[][] item = {{1,60,10}, {2,100,20}, {3,120,30}};
int limit = 50; //배낭의 제한 무게
//무게 대비 가치순으로 정렬
Arrays.sort(item, new Comparator<Integer[]>(){
@Override
public int compare(Integer[] o1, Integer[] o2) {
int prev = o1[1]/o1[2];
int cur = o2[1]/o2[2];
if((cur-prev)>0){
return 1;
}else{
return -1;
}
}
});
int result = 0;
for(int i = 0 ; i<item.length ; i++){
Integer[] cur = item[i];
if (limit > 0) {
if (limit >= cur[2]) { // 물건 무게가 제한 이하일 경우
limit -= cur[2];
result += cur[1];
} else { // 물건 무게가 제한 초과일 경우
result += (cur[1] / cur[2] * limit); // 잘라서 넣음
limit = 0;
}
}else {
break;
}
}
System.out.println(result); // 240
}
}결과
분할 가능 배낭 문제
지난 시간 동적 프로그래밍에서는 무게에 따라 물건을 넣거나 넣지 못하는 배낭 문제(0/1 배낭 문제)를 풀었습니다. 하지만 이번 시간의 배낭 문제는, 같은 배낭 문제이지만 물건이 무거울 경우 쪼개서 넣을 수 있습니다. 즉 무게가 초과할 거 같은면 물건을 쪼개서 일부만 넣을 수 있다는 것이죠.
지난 시난 시간에는 동적 프로그래밍으로 복잡하게 풀었다면, 이번에는 그리디 알고리즘으로 간단하게 풀 수 있습니다. 직관적으로 생각해봅시다. 물건을 쪼갤 수 있다는 가정 하에서는 무엇부터 넣는 게 최선일까요? 무게 대비 가치가 높은 것들을 먼저 넣는 게 좋겠죠?
지난 시간과 동일한 표입니다. 무게 제한도 50이고요. 하지만 지난 시간과는 달리 1번 물건을 먼저 선택하고, 2번, 3번 순으로 넣습니다. 3번은 무게 초과이기 때문에 20만큼만 쪼개서 넣으면 됩니다.
코드
package greedy;
import java.util.*;
public class GreedySelect {
public static void main(String[] args) {
//[number][startTime][endTime]
Integer[][] activity ={{1,1,3}, {2,2,5}, {3,4,7}, {4,1,8}, {5,5,9}, {6,8,10}, {7,9,11}, {8,11,14}, {9,13,16}};
//끝나는 시간이 빠른순서대로 정렬
Arrays.sort(activity, new Comparator<Integer[]>() {
public int compare(Integer[] arr1, Integer[] arr2) {
if( ((Comparable)arr1[2]).compareTo(arr2[2]) > 0 )
return 1;
else
return -1;
}
});
int last = 0;
ArrayList<Integer[]> result = new ArrayList<Integer[]>();
//가장 일찍 종료되는 것을 선택 -> 그 다음 조건에 맞는 빠른종료 활동 선택 (위에서 정렬했기때문에 조건에 맞는 것을 push 하면 됨)
for(int i = 0 ; i<activity.length ; i++){
Integer[] a = activity[i];
if(last<a[1]){
last = a[2];
result.add(a);
}
}
for(Integer[] a : result){
System.out.println(a[0]);
}
// 1 3 6 8
}
}결과
