Greedy Algorithms

Greedy Algorithms, 한국말로 탐욕(?) 탐색법이라고 하면 될 것 같다.

이 기법은 말 그대로 결정의 순간에 모든 경우를 보는게 아니라 당장 코앞의 문제에 최선의 선택을 하는 방식을 말한다.

당연히 전체를 보지 않기 때문에 최선이 아닌 경우가 많다. 오히려 이 기법이 통하지 않는 경우가 허다

그렇기 때문에 Greedy Algorithms으로 작성되면 그것이 최선의 선택이라는 것을 증명해야만 한다.

그리고 그 증명이 어렵다...

 

그렇다면 수강신청을 예시로 Greedy Algorithms을 작성해보자

예를 들어 신청할 수 있는 과목이 n개가 있고 각 과목의 시작시간과 끝시간이 있을 때, 가능한 많은 과목을 신청하고자 하면 어떤 과목들을 선택해야 할까?

일단 단순히 Backtracking으로 해당 과목을 선택할지 말지를 고려해서 모든 경우를 탐색해면 recursion으로 인해 O($2^n$)의 시간이 걸린다.

DP를 사용해서 memoization하면 O($n^3$)의 시간이 걸린다.

 

만약 Greedy Algorithms을 사용하려면 어떻게 해야 할까? 일단 다음과 같은 경우들로 Greedy Choice를 할 수 있을 것이다.

• 시작시각이 가장 이른 수업을 먼저 선택
• 짫은 수업을 먼저 선택
• 서로 겹치는 수업의 개수가 가장 적은 것을 먼저 선택
• 종료시각이 가장 이른 수업을 먼저 선택

GreedySchedule(S[1..n], F[1..n]): //S[]:시작시각, F[]:종료시각
	sort F and permute S to match
    count = 1
    X[count] = 1
    for i=2 to n
    	if S[i] > F[X[coutn]]
        	count = count + 1
            X[count] = 1
    return X[1..count]

수업들을 종료시각(F[i])이 이른 순서대로 정렬 후 차례대로 보면서 겹치지 않으면 선택한다.

시간복잡도는 O(nlogn)

그렇다면 이게 과연 정말 최선인지 '증명'해야 한다.

f를 가장 먼저 종료하는 수업이라고 하고 X를 최선인 스케쥴 배열이라고 하자. 그리고 f는 X에 포함되지 않는다고 까지 하자

g를 X에 포함된 것 중 가장 먼저 끝나는 수업이라고 하면 f는 가장 먼저 종료하는 수업이기 때문에 항상 g보다 먼저 끝난다 => 그렇다면 X에서 g를 빼고 f를 넣는 것이 가능하다 => 따라서 이걸 반복하다 보면 이 방식은 최선과 같다는 것을 알 수 있다.

 

이걸 일반화 해서 설명하면 {$g_1, g_2, ..., g_{j-1}, g_j, g_{j+1}, ..., g_k$} 가는 스케쥴이 greedy 스케쥴이고

{$g_1, g_2, ..., g_{j-1}, c_j, c_{j+1}, ..., c_k$} 을 최선인 스케쥴이라고 하자

즉 이 두 스케쥴은 j-1까지는 일치하고 그 이후부터 다른 스케쥴인 경우이다. 그리고 최선인 경우가 더 적을 수는 없으니까 k<=m

여기서 $c_j$를 빼고 $g_j$를 넣어보자 그러면 {$g_1, g_2, ..., g_{j-1}, g_j, c_{j+1}, ..., c_k$}가 되는데 겹치지 않고 그대로 최선인 경우가 된다. 왜냐하면 $g_j$는 가장 빨리 종료하는 수업들로 이루어져 있기 때문에 $g_{j-1}$ 이후로 가장 빨리 종료하는 수업이라서 $ c_{j+1} $와 겹치지 않는다. 따라서 이걸 반복하다 보면 greedy로 만들어진 스케쥴로 최선인 스케쥴임을 확인 할 수 있다.

* 만약 k<m이면 $c_{k+1}은 g_k와 겹지지 않고 이후에 시작하는 수업이 있는 것이고 그러면 greedy로 찾은 스케쥴이 덜 찾았단 소리가 된다. 따라서 k=m이어야만 하기 때문에 최선과 같다.