그리디?
그리디의 뜻은 '탐욕적인' 이라는 의미다.
매 선택에서 현재 당장 최적인 답을 선택해 나가는 방식.
추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다.
- 빠르게 근사치를 계산할 수 있다.🤩
- 부분 최적해로 전체적인 최적해가 아닐 수 있다.😞
그리디 알고리즘의 조건
- 탐욕 선택 속성 - 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다.
- 최적 부분 구조 - 부분 문제의 최적 결과가 전체에도 그대로 적용될수 있어야 한다.
여기서 2번 조건만 보면 DP와 비슷하지만 DP는 다음 선택에 이전 선택의 영향을 받기 때문에 1번 조건을 만족하지 않아 그리디와 다르다.
일반적으로 그리디임을 증명하려면 수학적 증명이 동반되어야 한다. 하지만 이 방식은 좀 어려우므로 우선 테스트 코드를 작성하여 정상 동작하는지를 알아보는 방식으로 시도하는 경우가 많다.
그리디가 아니라고 보는 경우의 반례를 1개만 찾아도 되기 때문에 상대적으로 쉽다.
예제1)거스름돈 문제
문제- 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다.
손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하세요. (단, 거슬러줘야 할 돈 N은 항상 10의 배수입니다.)
- 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
- N원을 거슬러줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러 준다.
- 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 된다.
- N=1260일 때의 예시
1250/500 = 2, 즉 500원 2개 거슬러주고 1250%500 = 260원 남음
260/100 = 2, 즉 100원 2개 거슬러주고 260%100 = 60원 남음
60/50 = 1, 즉 50원 1개 거슬러주고 60%50 = 10원 남음
10/10 = 1, 즉 10원 1개 거슬러주고 완료
이 문제의 경우 500원의 개수에 따라 뒤의 선택인 100원의 개수가 달라지므로 영향을 준다고 생각할 수 있다.
거슬러주는 동전의 상관 관계를 보면 100원은 500원의 약수이고, 50원은 10원의 약수이고, 10원은 50원의 약수이므로 상위의 동전이 하위의 동전 개수를 대체 할 수 있으므로 그리디를 적용할 수 있다.
만약 거슬러줘야하는 금액이 1200원이고 동전의 종류가 500원, 400원, 100원 이라고 하면,
그리디를 이용해서 풀면
500원 2개 + 400원 0개 + 100원 2개 : 총 4개가 나오지만
400원 3개 : 총 3개로 그리디의 결과가 최적해가 되지않는다. 이는 400원이 500원의 약수가 아니기 때문에 500원이 400원을 대체해 더 적은 개수로 반환하는 경우라고 보장할 수 없게 된다.
예제2)활동 선택 문제
문제- N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때, 한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제이다.
즉, 각각의 활동(Activity)에는 시간이 소요되므로 하나를 선택했다면 그 동안 해당 시간에 다른 Activity를 할 수 없다.
위에서 각 활동과 그것들의 시작 / 종료 시간이 설정되어 있는 것을 알 수 있다. 이 문제는 최대한 많은 활동을 해야 하므로 언제 시작하든 전체에서 가장 종료 시간이 빠른 것부터 선택 해야 한다.
따라서, 종료 시간을 기준으로 정렬한 뒤, 제일 먼저 끝나는 활동을 무조건 선택하고 끝났을 때, 바로 다음에 선택할 수 있는 활동을 찾아 수행하는 방식을 반복하여 해결할 수 있다.
import java.util.ArrayList;
import java.util.Collections;
class Activity {
String name;
int start;
int end;
public Activity(String name, int start, int end) {
this.name = name;
this.start = start;
this.end = end;
}
}
public class Main {
public static void selectActivity(ArrayList<Activity> list) {
// 종료시간 기준 오름차순 정렬
Collections.sort(list, (x1, x2) -> x1.end - x2.end);
int curTime = 0;
ArrayList<Activity> result = new ArrayList<>();
for (Activity item: list) {
// 활동의 시작 시간이 현재 시간보다 작으면 추가
if (curTime <= item.start) {
// 다음 활동 시간 비교를 위해 현재 활동의 종료 시간으로 업데이트
curTime = item.end;
result.add(item);
}
}
// 출력
for (Activity item: result) {
System.out.print(item.name + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Test code
ArrayList<Activity> list = new ArrayList<>();
list.add(new Activity("A", 7, 8));
list.add(new Activity("B", 5, 7));
list.add(new Activity("C", 3, 6));
list.add(new Activity("D", 1, 2));
list.add(new Activity("E", 6, 9));
list.add(new Activity("F", 10, 11));
selectActivity(list);
}
}