
[알고리즘] Activity selection : 정의 & d.p algorithm
Computer Science/algorithms
2021. 10. 27. 16:38
(2021.10.27) 알고리즘 수업들으면서 정리하기 15탄 Activity selection :공통의 자원에 대한 독점적인 사용을 필요로 하는 활동 N개가 있는데 이를 어떻게 스케줄링 할 것인가 하는 문제를 말한다. ex) 교실의 대한 사용을 스케줄링 하는 문제 Problem: 여러 competing activities 사이의 스케줄을 조정하는 것 ( 각 activity에 대해서 시작과 종료시간은 주어짐) Goal: nonoverlapping activities 의 largest possible set을 선택함 이를 이제 dynammic programming 기법으로 접근해보겠다 greedy algorithms으로 접근하는 건 다음 시간..