최적화 - 탐욕 알고리즘, activity selection problem

이전 글에서 최적화에 대한 개념에 대해 알아봤습니다. 이번 글에서는 대표적인 최적화 문제 중 하나인 An activity selection problem과 이를 해결하기 위한  Greedy-Algorithm 또는 탐욕 알고리즘에 대해 다뤄보도록 하겠습니다. 

 

An activity selection problem (활동 선택 문제)

 

활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 겹치지 않고 한 번에 가장 많은 수업들을 고르는 알고리즘입니다. 

 

	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11
시작시간	1	3	0	5	3	5	6	8	8	2	12
끝시간	4	4.5	6	7	9	9	10	11	12	14	16

 

위의 스케줄들을 가지고 가장 많은 개수의 일정을 만들어라는 문제가 주어졌습니다.

 

어떤 기준을 택하는 것이 합리적일까요?

1. 가장 짧은 시간을 택한다.
2. 다른 일정들과 가장 적게 겹치는 것을 택한다.
3. 가장 빨리 시작하는 것을 택한다.
4. 가장 빨리 끝나는 것을 택한다.
5. 가장 늦게 시작하는 것을 택한다.
6. 가장 늦게 끝나는 것을 택한다.

이 문제를 해결해 보기 앞서 탐욕 알고리즘에 대해 간단히 알아보겠습니다. 간단히 말하자면 미래의 상황을 고려하지 않고 현재 가장 좋아 보이는 선택을 하는 방법입니다. 각 단계별로 취할 수 있는 최선을 택할 뿐입니다. 가끔씩 이러한 방법이 효과적일 수 있지만 대부분의 경우 그렇지 않습니다. 강아지에게 간식 하나를 두고 기다려 훈련을 한 뒤 정해진 시간 동안 기다리면 2배의 보상을 주는 경우를 살펴봅시다. 강아지가 조금만 기다린다면 2배의 보상을 얻을 수 있음에도 당장 현재 눈 앞에 간식의 유혹을 참지 못하고 먹어버리게 되는 것이죠. 그래서 탐욕 알고리즘이라고 불리는 이유이기도 합니다. 

 

다시 활동 선택 문제로 돌아와 6개의 기준에서 4번 가장 빨리 끝나는 것을 택해보겠습니다. 

 

- 가장 빠른 시간인 4시 끝나는 시간인 A1을 택하겠습니다. A1을 택하면서 겹치는 시간대인 A2, A3, A5, A10를 택할 수 없게 되었습니다. 남은 것은 A4 [5,7], A6 [5,9], A7 [6,10], A8 [8,11], A9 [8,12], A11 [12,16]입니다.

- A1 이 끝난 4시 이후 일정 중 가장 빨리 끝나는 A4 [5,7]을 선택하겠습니다. A4를 택하면서 A5, A6, A7들이 겹쳐 선택할 수 없고 남은 것은 A8 [8,11], A9 [8,12], A11 [12,16]입니다.

- A4가 끝난 7시 이후 일정 중 가장 빨리 끝나는 A8 [8,11]을 선택하겠습니다. A8을 택하면서 A9 가 겹쳐 선택할 수 없고 남은 것은 A11 [12,16]입니다.

- A8이 끝난 11시 이후 일정 중 가장 빨리 끝나는 A12 [12,16]을 선택하겠습니다. 이후 남은 일정은 없습니다.

 

가장 빨리 끝나는 일정을 선택한 후 A1, A4, A8, A11의 일정을 만들었습니다. 

 

이 탐욕 알고리즘은 O(nlon)의 시간이 걸립니다. 이 Big-O 표기법에 대해서는 다음에 다루도록 하겠습니다. 탐욕 알고리즘은 매우 속도가 빠릅니다. 왜냐하면 간단하기 때문이죠. 그런데 왜 이 빠르고 간단한 알고리즘이 별로일까요? 위에서 말했듯이 가끔 효과적일 뿐 대부분 틀리기 때문입니다. 

 

탐욕 알고리즘의 문제점은 locally-optimal choice라는 것입니다. 당장 현재만을 고려해 현재의 최선이 미래에는 최악의 결과가 될 수 있기 때문입니다. 강아지 기다려 훈련에서 현재 할 수 있는 최선을 선택을 했는데 최악의 결과가 나와버렸죠.