[알고리즘] 그리디 알고리즘/탐욕 알고리즘(Greedy Algorithm)

지금 앞에 놓인 상황에서 최선의 선택을 고르는 것
이로 인해 최적의 해를 보장하지 않음
최선의 선택을 고르게 하기 위해 정당성 증명을 해야 함
아래처럼 문제를 보고 선택할 수 있는 가장 최적의 경우를 만들어줘야 함
(상세 내용은 아래 더보기를 통해 확인 가능)

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.[1] 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

 

그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체문제의 해답이 될 때 사용 할 수 있다. 위 서술 같은경우는 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한경오니 당연히 최적해를 보장해주지 못한다.

 

[나무위키]

문제1. 회의실 배정

문제 : 회사에 회의실이 하나밖에 없는데, n(<=100)의 팀이 각각 회의하고 싶은 시간을 다음 그림과 같이 제출했다고 한다. 두 팀이 동시에 회의실을 같이 쓸 수 없는 경우 최대로 많은 회의를 진행할 수 있는 최적해를 구하시오.

방법1. 회의시간이 짧은 회의를 먼저 배정한다?

회의 시간이 짧은 회의를 먼저 배정하는 경우 위 그림과 같은 상황에서 최적해를 구할 수 없다. 따라서 다른 방법이 필요하다!

방법2. 일찍 시작하는 회의를 배정한다?

일찍 시작하는 회의를 배정할 경우 다음과 같은 상황에서 문제가 된다. 그럼 이러한 상황에 봉착했을 때를 대비하여 다른 Case를 고려하여 선택하면 되지 않나? 안타깝지만 그런 방법은 좋지 않다. 반례는 또다른 반례의 반례를 낳기 때문에 더 좋은 방법을 찾는 것이 중요하다.

방법3. 일찍 종료하는 회의를 배정한다?

▶정답

실습문제 : 백준 1931번:회의실 배정

 

1. 일찍 종료하는 회의 순으로 Sort
   1. 단, 종료시각이 같을 경우에는 시작 시간이 빠른 것이 우선순위를 가짐
   2. (2,10) (3,10) 일때 2,10이 더 빠름
2. Sort 결과를 가지고 차례대로 계산
   1. IF 회의실을 사용하고 있는 팀의 종료시각 < 비교대상 팀의 시작시간
      1. ++ 회의가능팀

처음엔 bubble sort로 시도했으나, 시간 초과오류가 떠서 이외에 효과적인 방법이 무엇이 있을까 

고민하다 Comparable을 사용하기로 했다. [상세내용]

객체를 비교할 때 Comparable interface를 상속받아 compareTo를 구현하여 사용할 수 있음

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//회의실문제
//https://www.acmicpc.net/problem/1931
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = Integer.parseInt(scan.next()); //회의 수
		List<Meeting> meetingList = new ArrayList<>();
		for(int i=0; i<n; i++) {
			Meeting m = new Meeting();
			m.setStart(Integer.parseInt(scan.next()));
			m.setEnd(Integer.parseInt(scan.next()));
			
			meetingList.add(m);
		}
		
		//정렬
		Collections.sort(meetingList);
		
		//계산
		int endTime = meetingList.get(0).getEnd();
		int possibleNum = 1;
		
		for(int i=1; i<n; i++) {
			if(endTime <= meetingList.get(i).getStart()) {
				endTime = meetingList.get(i).getEnd();
				++ possibleNum;
			}
		}
		System.out.println(possibleNum);
	
	}
}

class Meeting implements Comparable<Meeting>{
	int start;
	int end;
	public int getStart() {
		return start;
	}
	public void setStart(int start) {
		this.start = start;
	}
	public int getEnd() {
		return end;
	}
	public void setEnd(int end) {
		this.end = end;
	}
	
	//종료시간 기준
	public int compareTo(Meeting m) {
		if(this.getEnd() == m.getEnd()) {
			if(this.getStart() < m.getStart()) {
				return -1; 
			}
			return 1;
		}else if(this.getEnd() < m.getEnd()) {
			return -1;
		}else {
			return 1;
		}
 	}
	
	
}

 

---

참고 : jjg2362.log