
[알고리즘] Activity Selection : greedy algorithm
Computer Science/algorithms
2021. 11. 3. 22:57
(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이 더..