Activity-Selection-Problem(활동 선택 문제)
활동 선택 문제는 주어진 시간 내에 최대한 할 수 있는 활동의 개수를 묻는 문제이다.
예를 들어서 당신이 전시회에 놀러갔을 때 여러 활동들이 있다고 가정하자. 이때 각 활동들은 시작 시간과 종료 시간이 다르고 활동에 참여하면 중간에 나올 수는 없다. 최대한 많은 활동들을 하고 싶을 때 최대 몇 개의 활동을 할 수 있는가?
를 묻는 것이 활동 선택 문제이다.
이때 Input은 활동 집합의 시작 시간과 종료 시간이다. 단, 종료 시간은 오름차순으로 정렬한다. (안 되어 있다면 정렬해주어야 한다.)
•
예시
위의 예시에서 를 선택할 수 있다.
그러나 을 선택한다면 더 많은 활동을 할 수 있다. 따라서 후자가 더 좋은 선택이다.
해결 알고리즘
그리디 알고리즘(Greedy Algorithm)을 이용해 결과를 도출할 수 있다.
다만, 일반적인 그리디 알고리즘의 특성처럼 최적의 경우를 구할 수는 있지만 모든 최적의 경우를 전부 다 구할 수는 없다. (최적의 경우 중 한 가지만 구할 수 있다)
해결 방법의 포인트는 현재 시간을 기준으로 할 수 있는 끝나는 시간이 가장 빠른 활동만을 하는 것이다.
예를 들어 위의 예시에서는 처음에 가장 빨리 끝나는 것은 이다. 그리고 그 다음 가능한 활동들 중 가장 빨리 끝나는 것은 이다. 왜냐하면 시작 시간이 4이상이고 끝나는 시간이 가장 작은 것은 이기 때문이다.
증명
만약 어떤 시간 이후 다음 활동을 고른다고 하자. 그러면 가능한 경우는 두 가지이다.
1.
끝나는 시간이 가장 빠른 활동을 선택하는 경우
2.
끝나는 시간이 가장 빠른 활동이 아니라 다른 활동을 선택하는 경우
만약 2를 선택했고 다행히 최적의 경우가 나왔다고 하자. 그럼 이때 끝나는 시간이 가장 빨랐던 활동을 활동1, 2에서 선택했던 다른 활동을 활동2라고 하자.
예를 들어서 활동1은 1~4, 활동2는 2~5라고 하자.
그런데 최적의 경우 조합에서 활동2는 활동1으로 대체해도 무방하다. 왜냐하면 어차피 끝나는 시간은 5 이전이므로 활동2를 선택했을 때 뒤이어 했을 활동들에 영향을 미치지 않는다. 오히려 시간이 비기 때문에 여유가 생긴다.
다시 말해, 현 상황에서 선택할 수 있는 가장 빠른 활동을 선택하지 않는 경우가 있다해도, 그것은 가장 빠른 활동을 선택한 경우로 대체가 가능하다.
따라서 계속해서 종료가 가장 빠른 활동들만 선택하면 그 조합은 최적의 경우가 될 수밖에 없다.