Greedy Algorithm (탐욕 알고리즘)
일들의 수행시간이 서로 겹치지 않으면서 일을 되대로 많이 할 수 있도록 스케쥴링하는 문제.
Greedy 말그대로 탐욕 알고리즘은, 매 순간마다 최선의 선택을 하는 그런 알고리즘이다.
즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해 가며, 최종적인 답을 구하는 알고리즘이라 할 수 있다.
그러나, 이 알고리즘을 설계 할 때 유의할 점은 전체를 고려하는 게 아니라 문제를 부분적으로 나누고, 나누어진 문제에 대한 최적의 해답을 구함으로써, 전체적인 최적의 해가 될 수 있는 경우를 찾는 방법이다.
유의할 점은, 매 순간마다 최선의 선택을 하여 나온 해가 반드시 전체적인 최적해는 아니라는 것이다. 그렇기 때문에, 탐욕 알고리즘을 사용할 때에는 전체적인 최적해 인지를 항상 염두에 둘 필요가 있다.
이 알고리즘의 응용으로, 다익스트라 최단 경로 알고리즘이나 최소 비용 신장트리 혹은 배낭채우기 문제등에 이용한다.
알고리즘
1. 해 선택(Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다.
2. 적절성 검사(Feasiblity Check) : 새로운 부분해 집합이 적절한지 검사한다.
3. 해 검사 (Solution Check): 새로운 부분해 집합이 문제의 해가 되지는지 검사한다. 아직 문제의 해가 완성되지 않았다면, 1번부터 다시 시작한다.
<풀이 방법>
1. 강의시간을 시작시간 기준으로 정렬한다.
2. d를 그리디 알고리즘으로 할당된 강의실의 갯수라고 한다.
3. d번째 강의실은 d-1 번째 강의실에 배정된 강의와 강의 시간이 겹치는 강의가 생겼을때 할당한다.
4. 이러한 d번째 할당은, 각각의 Start Job 이후에 발생한다.
5. 시작시간 순으로 정렬했기 때문에, 강의가 겹치는 일은 Start Job 이후에 시작되지 않는 강의에 의해서 발생한다.
※ Key Observation
Number of classrooms needed >= depth
(필요한 강의실의 수는 최소한 특정한 시간에 겹치는 강의의 갯수 이상이다.)
예제 문제 ) 강의실 할당
https://www.acmicpc.net/problem/1374
문제
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이 때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.
물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이라고 가정한다.
출력
첫째 줄에 필요한 최소 강의실 개수를 출력한다.
예제 입력
8
6 15 21
7 20 25
1 3 8
3 2 14
8 6 27
2 7 13
4 12 18
5 6 20
출력
5