[문제해결기법] 5. 욕심쟁이 기법

1. 욕심쟁이 알고리즘 : Greedy algorithm

매 단계마다 각 단계에서 최선의 선택을 한다. (현재 순간마다)

알고리즘이 매우 간단하나, 구한 답이 정답인지 검증이 필요하다.

 

기본 형태

2. 회의실 배정 문제

한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해서 시작 시간 Si와 끝 시간 Fi가 주어진다. 각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하시오.
❖ 입력 ➢ 첫 줄에는 회의의 수 n
            ➢ 둘째 줄부터 n+1줄까지 두 정수 Si와 Fi
❖ 출력 ➢ 잡은 회의를 차례대로 출력(둘 이상의 답이 있을 수 있음)

 

가능한 접근 방법

- 회의시간이 짧은 것 부터 넣는다 -> 반례 존재

- 다른 회의와 가장 적게 겹치는 회의부터 넣는다 -> 반례 존재

- 가장 빨리 끝나는 회의부터 넣는다!!

 

증명

회의들을 끝나는 시간에 따라 정렬하여 회의 번호를 {1 , ... , n} 이라고 하자. 그러면 정답은 1을 포함하거나 포함하지 않는다.

정답이 1을 포함하지 않는다면,

정답의 첫 답이 1과 겹치지 않는다면, 1을 넣어서 답을 더 길게 만들 수 있으므로 모순이다.

정답의 첫 답이 1과 겹친다면, 첫번째 답은 여전히 1보다 늦게 끝나므로 이를 빼고 1을 넣으면 여전히 답이 된다.

따라서 정답은 반드시 1을 포함한다고 할 수 있다.

이제 1을 제외한 나머지 구간에 대해서 답을 구하면 된다.

 

 

3. 가장 가까운 점 : closest pair

n개의 2차원 점이 주어지고, 가장 가까운 두 점 사이의 거리를 구하는 문제이다. (x1-x2)^2 + (y1-y2)^2

 

(1) O(n^2 log n)

가장 단순한 알고리즘으로, 모든 경우를 다 구한뒤 오름차순 정렬하여 첫 값을 반환.

모든 거리를 구하는데에 O(n^2), 정렬에 O(n^2 log n)

 

(2) O(n log n) : 분할 정복

일단 점들을 x좌표 기준으로 정렬하고, 가운데 점을 기준으로 왼쪽/ 오른쪽으로 나눈다. (반복)

정렬은 O(n log n)이 걸리지만 O(n)시간에 가운데 점만 알아낼 수 있음.

 

가장 가까운 점의 쌍은 다음 3가지 중 하나일 것이다.

- 왼쪽 부분의 가장 가까운 쌍

- 오른쪽 부분의 가장 가까운 쌍

- 한 점은 왼쪽에, 한 점은 오른쪽에 있는 가장 가까운 쌍

 

제일 헷갈렸던 부분

 

여기서 최대 4개의 점만 고려하면 되는 이유는,

만약 저 사각형에서 왼쪽 아래의 점을 고려한다면,

오른쪽 점들 중에서 각 변이 d인 저 사각형 내부에는 꼭짓점인 4개의 점까지만 존재할 수 있고

점이 더 존재한다면 애초에 최소 거리가 d보다 작기 때문에 모순이다.

따라서 한 점은 왼쪽에, 한 점은 오른쪽에 있는 가장 가까운 쌍을 찾을 때 최대 4n시간이 걸림. -> O(n)

 

그리고 분할정복을 재귀적으로 진행하기 때문에

결과적으로 시간복잡도는

T(n) = 2*T(n/2) + O(n) => O(n log n) 이다.