[Algorithm] 정렬을 이용한 문제풀이

★스윕 라인 알고리즘 : 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링 하는 방법이다. 예를 들어 특정일에 손님들이 한 음식점을 언제 방문했고 언제 떠났는지에 대한 정보를 모두 알고있다고 할 때, 동시에 존재하는 모든 손님들의 수의 최대값을 구하는 문제가 있다. 손님의 방문과 떠남이라는 두 가지의 이벤트를 만들어 이를 시간 순으로 정렬하여 차례로 살핀다. 이 알고리즘의 수행시간은 이벤트를 정렬하는 데 드는 O(n log n)시간 + 스윕 라인을 수행하는데 드는 O(n)시간이 들어 총 O(n log n)이 걸린다.

★이벤트 스케줄링 : 입력 데이터를 정렬한 후 탐욕법 기반의 전략으로 해를 구하여 푼다. 예를 들어 한번에 한 팀씩만 사용할 수 있는 회의실에서 n개의 팀이 각자의 시작 시각부터 종료 시각까지 회의하려고 하고, 회의실의 개방시간과 폐쇄시간이 주어질 때, 회의 할수 있는 팀 수의 최대값을 구하는 문제가 있다. 이 경우 회의들을 여러가지 기준으로 정렬할 수 있는데 종료시간 순으로 정렬하여 차례로 선택하는 알고리즘으로 항상 최적해를 찾을 수 있다는 것이 알려져있다. 왜냐하면 굳이 더 늦게 끝나는 회의를 선택할 경우 결과가 더 좋아질 수는 없기 때문이다.

★작업과 데드라인 : 작업 n개의 소요시간(s)과 데드라인(d)이 주어질 때, 작업의 수행 순서를 구한다. 작업의 종료시간을 t라고 할 때 작업이 종료되었을 때 d-t점을 얻게 된다. 얻을 수 있는 최대 점수는 몇 점인가? 이 문제는 작업을 소요시간 순으로 오름차순으로 정렬한 순서대로 수행하여 최적해를 찾는다. 두 개의 연달아 작업을 수행할 때 소요시간이 긴 작업을 먼저 수행한다면 두 작업의 순서를 바꾸는 것이 더 좋은 점수를 얻을 수 있기 때문이다.