[알고리즘] Activity-selection-problem / 그리디 알고리즘

Activity-selection-problem이란?

Expo 전시회에 놀러간 당신. Expo에는 여러 activity(활동) 들이 있다. 

activity들은 각각 시작시간과 종료시간이 다르고,

먼길 걸어 온 전시회이므로 당신은 최대한 많은 활동들을 즐기고 돌아가고 싶다.

activity들의 정보(activity의 시작 시간, 종료 시간) 를 보고 최대 몇개의 활동을 할 수 있을지 어떻게 구할까??

 

Input : activity 집합 의 시작 시간, 종료 시간. (s_i, f_i)

*조건 : 종료 시간은 오름차순 정렬이 되어 있다! (정렬 안되어있으면 직접 정렬하면 됨)

예시)

예를들어 3번째 activity 는 0분에 시작하여 6분에 끝난다. ( 시간은 분이라고 치자)

 

활동들을 즐기는 방법은 다양하다. 

{a3, a9, a11}  ( a3 -> 0~6 , a9 -> 8~12 , a11 -> 12~16) 를 즐길 수도 있고

{a1, a4, a8, a11} 을 즐길 수도 있다.

우리는 더 많은 활동을 할 수 있는 후자 의 경우가 더 좋고, 최대한 많은 활동을 즐기는 경우를 알고 싶다.

 

---

해결 알고리즘

이는 그리디 알고리즘을 이용해 아주 빠르고 효율적이고 좋은 결과를 도출 할 수 있다!!

하지만 최적의 경우를 구할 수는 있지만 모든 최적의 경우를 다 구할 수는 없다. (최적의 경우 중 한 가지만)

 

이 해결 방법을 쉽게 설명하자면

현재 시간을 기준으로 할 수 있는 끝나는시간이 가장 빠른 활동만을 계속 하는 것이다.

시작할 때는 가장 먼저 끝나는 4분에 끝나는 활동(위 예시, 활동1) 하고, 그 다음에는 4분 이후에 시작하는 결과들 중 가장 빨리끝나는 활동(활동4) 하고 이런식으로 계속 하는게 최적의 해라는 것이다.

---

위 알고리즘의 증명

 

만약 활동1을 포함하지 않는 다른 최적의 해가 있다고 치자. 그 최적의 해는 최소한 4초 이후에 끝나는 활동 하나는 했을 것이다. 그런데 그 활동은, 활동1로 대체해도 똑같다! 

쉽게 말하자면  활동1(1초시작, 4초끝) 을 포함 하지않고 활동2(3초 시작 5초끝) 들어가는 최적해가 있다?

그 최적해는 활동2를 활동1로 대체해도 우리가 할 수 있는 활동의 수는 그대로 이라는 것이다.

한번만 다시 말하자면, 현 상황에서 선택할수 있는 가장 빠른 활동을 선택하지 않는 경우가 있다해도, 그것은 빠른 활동을 선택한 경우로 대체가 가능하다.

따라서, 그리디 알고리즘을 통해 해결한 이 최적해는 항상 최다 활동의 수가 될 수 밖에 없는 것이다. (공동 1위는 나올 수 있음)

위 증명에 대한 이론적 설명

 

---

수도코드화

위 알고리즘은 코드가 보다시피 엄청나게 간단하다.

이런 문제를 다이나믹 방법으로 해결하는 코드를 짜려면,, 어휴 상상하기도 싫다.

이처럼 그리디 알고리즘으로 속도, 난이도 면에서 쉽게 짤 수 있는 문제들이 많다. 다이나믹 프로그래밍 하기전에 한번 더 생각해보는게 좋을듯 하다.

 

 

출처 : 출처 : 고려대학교 정순영 교수님 알고리즘 수업,

introduction to algorithms 3rd edition - 토머스 H. 코르먼(Thomas H. Cormen) 찰스 E. 레이서슨(Charles E. Leiserson)