[알고리즘] Interval Scheduling

알고리즘 수업을 들으면 Greedy 알고리즘의 첫 번째 예로 살펴보는 것이 바로 이 interval scheduling 문제이다. 작업 목록과 각 작업을 수행할 수 있는 시간 구간이 주어진다. 그리고 최대 몇 가지 작업을 할 수 있는지를 알아내는 문제이다. 실제로 선택되는 작업들이 유일하지 않을 수도 있다. 쉬운 예를 들어보자.

  

T1: 1시-3시 청소

T2: 2시-4시 숙제

T3: 3시-5시 낮잠

T4: 4시-8시 운동

T5: 7시-9시 TV시청

T6: 8시-9시 옆집가기

위의 각각의 작업은 주어진 시간을 꽉 채워 사용해야하고 그 때에만 가능하다고 하자. 최대 다양한 작업을 하기 위해서는 1시-3시에는 청소(T1), 3시-5시에는 낮잠(T3)을 자고, 7시-9시에 TV를 보면(T5) 된다. 다른 방법(T2, T4, T6)도 하나 있지만 어쨌든, 최대 3가지 작업을 할 수 있다. 작업이 몇 개 안되면 대충 눈으로 비교해보면 쉽게 알 수 있지만 일이 100가지, 1000가지가 된다고 해보자. 쉽게 풀 수 없다. 

물론 컴퓨터를 이용하면 사람보다는 좀 더 빠르게 풀 수 있을 것이다. 일단, 무식하게 생각해서 각 작업이 결과에 포함하거나 않거나 하면 되고, 모든 경우의 수 중에서 시간이 중복되는 작업이 없는 경우의 목록의 개수가 가장 큰 경우를 찾으면 된다. 작업의 종류가 n가지라면 최대 2ⁿ가지 종류가 나온다. 대략 n=100만 되어도, log2¹⁰⁰=30.1이므로 10³⁰이 넘는 경우의 수가 나온다. 좀 많다. 좀 더 효과적인 방법을 고안해 내는 게 알고리즘을 연구 혹은 공부하는 사람들이 밥 먹고 하는 일이다. 그 사람들이 무엇을 발견(?)했는지 살펴보자.

일단, 가장 먼저 끝날 수 있는 작업을 선택한다. 이제 그 작업이 끝나는 시간 이후에 시작할 수 있는 작업들 중에서 가장 먼저 끝날 수 있는 작업을 택한다. 또 다시, 그 작업이 끝나는 시간 이후에 시작되는 작업 중에서 가장 빨리 끝날 수 있는 일을 택한다. 이런 식으로 택하다보면 가장 많은 작업을 택할 수 있게 된다. 프로그래밍을 하자면, 현재 시점에서 가장 빨리 끝날 수 있는 작업을 찾기 위해서는 현재 시점에서 실행 가능한 작업 목록에서 작업 시작 시간을 기준으로 정렬을 먼저 한 후 찾으면 효율적이다. 

Greedy 알고리즘은 현재 시점에서 최선의 선택을 한 것이 결과적으로 문제 전체의 최선의 선택이 된다는 것이다. 그 때 그때 Local optimal을 선택하면 결국 global optimal을 찾을 수 있다는 말이다.

다음 문제는 위 문제보다 조금 더 복잡해 보이는 문제이다. 각 작업에 가중치(weight)를 줘보자. 경제학 용어를 쓰자면 효용이라고 하면 되려나?

T1: 1시-3시 청소 - 10

T2: 2시-4시 숙제 - 50

T3: 3시-5시 낮잠 - 20

T4: 4시-8시 운동 - 20

T5: 7시-9시 TV시청 - 10

T6: 8시-9시 옆집가기 - 10

효용가치가 높은 작업 해야 하는 것이 당연하고, 주어진 시간 내에 최대 효용을 얻는 행동을 하는 것이 경제적인 인간이 마땅히 해야 할 일이다. 따라서 위 문제는 최대 효용을 얻기 위하여 어떠한 작업들을 해야 하는지에 대한 문제가 된다. 앞의 문제는 이 문제에서 모든 작업의 효용이 같다고 전제하면 동일한 문제가 된다. 그렇다면, 이 문제를 앞과 동일한 방법으로 풀 수 있을까? 안 된다. 일단 앞의 풀이처럼 T1, T3, T5를 선택하면 효용이 총 10+20+10=40이지만, T2, T4, T6을 선택하기만 해도 효용이 총 50+20+10=80이 된다. 후자를 택하는 것이 더 효율적이지만 앞의 알고리즘은 전자를 택하므로 항상 옳은 결과를 가져온다고 볼 수 없다. 

또 알고리즘을 연구하신 분들의 도움을 받자. 이번에는 greedy 알고리즘이 아니라, 또 하나의 유명한 문제 해결 기법인 dynamic programming (동적 프로그래밍)을 사용해보자. 이번에는 끝나는 시간으로 오름차순 정렬을 한다. 이 작업들을 각각 T[i]라고 하자. v[i]를 첫 번째 작업에서 부터 i번째 작업까지를 고려할 때 얻을 수 있는 최대 효용이라고 해보자. i번째 작업의 효용은 w[i]라고 하자. 

일단, v[1]은 w[1]이 된다. 이제 v[1]에서 v[i-1]이 올바른 값을 가지고 있다고 가정하자. 이제 v[i] 값은 어떤 값이 될지 생각해보자. v[i]는 (1) i번째 작업이 시작하는 시간보다 해당 작업의 끝나는 시간이 더 빠른 작업까지를 고려했을 때의 최대 효용에 w[i]를 더한 값과, (2) 그냥 i-1번째 작업까지를 고려했을 때의 최대 효용 중에 큰 값을 갖게 된다. 

왜 그렇게 될까? (1)을 살펴보자. i번째 작업의 효용 w[i]를 포함시키기 위해서는 i번째 작업과 이전의 어떤 작업도 중복되어서는 안 된다. i<j인 경우 v[i]<=v[j]가 늘 성립하므로, 그러한 값 중에 가장 큰 작업을 찾아 w[i]를 더하면 i번째 작업을 포함하는 최대의 효용이 나온다. (2)의 경우 i를 포함하지 않는 경우를 생각하는 것이다. 그렇다면 최대 효용은 i-1번째 작업까지를 고려한 경우가 된다. w[i]를 더하기 전의 (1)과 (2)는 같을 수도 있다. i를 첫 번째 작업부터 마지막 작업까지 구하면, v[n]이 바로 우리가 원하는 결과가 된다.

알고리즘은

1. 어떤 알고리즘을 써야하는지 알기 어렵고,
2. 그 알고리즘이 왜 옳은지 알기 어렵고,
3. 새로운 알고리즘을 만드는 것은 더 어렵다.

남에게 설명하지 못하는 것은 이해하지 못한 것과 같다.
설명을 하려고 노력하면, 그만큼 나의 이해도도 높아지리라 믿는다.
블로그를 그런 용도로 써봐야 겠다. ㅎㅎ