Algorithm: 욕심쟁이 기법

욕심쟁이 기법은 최적해를 구하는데에 사용되는 알고리즘중 하나로, 매 단계에서 가장 최선의 선택을 하여 최종 결과물이 최적해에 가까워 지도록 하는것이다.

욕심쟁이 기법은 매우 직관적이며 구현하기 쉽지만 최적해를 보장하지는 않는다.

 

예시) 회의실 배정 문제

한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해 시작시간 Si 와 끝시간 Fi 가 주어진다. 각 회의가 겹치지 않으면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하라.

 

해법: 가장 빨리 끝나는 회의부터 넣는다. 

증명: 

• 회의들이 끝나는 시간에 따라 {1,...,n} 이라고 하자.
• 정답은 1을 포함하거나 포함하지 않는다.
• 1을 포함하지 않는다면...
  • 정답의 첫번째 답이 1과 겹치지 않는다면 1을 넣어 답을 하나 더 길게 만들 수 있다
  • 정답의 첫번째 답이 1과 겹친다면, 첫번째 답은 1보다 늦게 끝나므로 이를 빼고 1을 넣어도 여전히 답..
  • 즉, 1을 반드시 포함한다.

가장 가까운 점

Brute Force Algorithm

• 모든 가능한 경우를 다 구한 뒤 ,오름차순 정렬하여 가장 첫 원소의 값을 출력
• 시간복잡도: O(n^2 log n)

O(n log n) 시간

• 모든 점을 x 좌표를 기준으로 정렬
• 정렬된 점들을 가운데 기준으로 나눈다
• 왼쪽 절반과 오른쪽 절반에 대해 각각 가장 가까운 두 점의 거리를 재귀적으로 구함
• 왼쪽 절반과 오른쪽 절반에서 구한 가장 가까운 두 점의 거리 중 최소값을 구함
• 중앙선을 기준으로 좌우에 위치한 점들 중에서 가장 가까운 두 점의 거리를 구함
• 4,5번중 더 작은 값
•