[알고리즘] Activity Selection : greedy algorithm

(2021.11.03)

알고리즘 수업들으면서 정리하기 16탄

 

w9-2 강의

activity selection을 greedy algorithm으로 푸는 방법을 배웠당

 

---

 

Activity Selection : greedy algorithm

 

 

 

d.p는 subproblem이 두개가 나오지만, greedy algorithm은 subproblem이 하나만 나온다.

 

 

 

aj와 am이 다른 경우에 Ak'를 정의하게 되는데

Ak'은 Ak에서 aj를 빼고, am을 넣은 것이라고 생각하면 된다.

 

Ak'의 activity들이 서로 오버랩되지 않는다는 것이 중요하다.

am은 Sk에서 가장 빨리 끝나는 activity이고, aj는 Ak에서 가장 빨리 끝나는 activity이다. 그렇기 때문에 am이 aj보다 빨리 끝날 것이다.(am이 더 빨리 끝나거나 aj랑 동시에 끝나거나) (Ak가 Sk의 optimal solution이라서 Sk가 Ak보다 더 포괄적이기 때문) 그래서 Ak'의 activity들은 서로 오버랩되지 않고, Ak'과 Ak에 속하는 activity들의 개수는 동일하다. 

결국 Ak'은 am을 포함하는 Sk의 optimal solution이 된다고 할 수 있는 것이다.

 

 

 

 

 

• start시간과 finish시간은 s와 f array 에 저장한다.
• finish time은 빨리끝나는 순서대로 정렬한다. (f1 ≤ f2 ≤ f3 ≤ ... ≤ fn)
• 가상의 a0를 넣어주는데, a0의 f0=0 이다.

 

 

출처: 교수님 강의노트

 

 

 

위와 같이 greedy algorithm으로 recursive하게 해결할 수 있다.

교수님이 보여주신 예시를 위의 코드를 바탕으로 풀어봤다.

 

 

 

 

 

 

performance of activity selection

 

ak와 오버랩되지 않는 am을 찾을 때까지 ak+1, ak+2, ..., an 을 차례대로 체크한다.