📖 탐욕 알고리즘

---

• 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적 방법
• 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라 생각되는 것을 선택해 나가는 방식
  • 최종적으로 답에 도달
• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 구한 최종적인 해답이 최적이라는 보장 없음

💬 대표적인 문제

---

◾ 회의실 배정하기

사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다. 회의는 시작 시간과 종료 시간이 있으며, 시간이 겹치는 회의는 동시에 열릴 수 없다. 최대 몇 개의 회의를 배정할 수 있을까?

• 회의 개수 : 10
• 시작, 종료 시간
  1 4 1 6 6 10 5 7 3 8 5 9 3 5 8 11 2 13 12 14

탐욕 알고리즘 적용

• 회의 목록에서 가장 일찍 끝나는 회의 a 선택
• a와 겹치는 모든 회의를 회의 목록에서 삭제
• 회의 목록에 회의가 다 없어질 때까지 1번 부터 반복

정당성 증명

• 탐욕적 선택이 항상 최적해로 가는 길 중 하나
• 즉, 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재

💻 알고리즘 구현

static class Time {
	int start, end;
	public Time(int start, int end) {
		this.start = start;
		this.end = end;
	}
}
static int lastEnd, cnt;
public static void main(String[] args) {
	Time[] mittings = {
			new Time(1, 4),
			new Time(1, 6),
			new Time(6, 10),
			new Time(5, 7),
			new Time(3, 8),
			new Time(5, 9),
			new Time(7, 9),
			};
	
	Arrays.sort(mittings, (m1, m2) -> m1.end - m2.end);

	lastEnd = 0; // 마지막으로 끝난 회의 종료시간
	cnt = 0;
	Arrays.stream(mittings).forEach(m -> {
    	// 마지막 회의 종료시간보다 시작시간이 같거나 커야함
		if(m.start >= lastEnd) { 
			System.out.print(m.start+"-"+m.end+" ");
			lastEnd = m.end;
			cnt++;
		}
	});
	System.out.println();
	System.out.println(cnt);
}

◾ Baby-gin 문제

0~9의 숫자 카드가 있다. run, triple 조사해서 baby-gin이 가능한지 확인해보자.

• run : 3개 연속으로 증가하는 숫자 카드가 있는 경우
• triple : 동일한 숫자 카드 3개가 있는 경우
• baby-gin : run+triple 이 있는 경우

탐욕 알고리즘 적용

• 숫자 카드의 개수가 담긴 count 배열 생성
• triple 먼저 판단한 후 run 판단

💻 알고리즘 구현

public static void main(String[] args) {
	int[] card = {3, 3, 3, 2, 3, 4};
	
	int[] cnt = new int[10];
	Arrays.stream(card).forEach(c -> cnt[c]++);
//		Arrays.stream(cnt).forEach(c -> System.out.print(c));
	
	int tripple = 0, run = 0;
	for (int i = 0; i < 10; i++) { // cnt 하나씩 돌면서 확인
		// tripple일 경우
		if(cnt[i] >= 3) {
			cnt[i]-= 3;
			tripple++;
		}
		// run일 경우
		else if(cnt[i] > 0 && cnt[i+1] > 0 && cnt[i+2] > 0) {
			cnt[i]--;
			cnt[i+1]--;
			cnt[i+2]--;
			run++;
		}
	}
	
	if((tripple+run) / 2 > 0) 
		System.out.println("가능");
	else System.out.println("불가능");
}