[고급 알고리즘] Greedy: Activity Selection Problem

1. Activity Selection Problem (활동 선택 문제)

• 한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.
• 한 사람이 동시에 두 가지 활동을 참여할 수 없습니다.

 

해결 방법

• 가장 먼저 끝나는 활동부터 선택합니다.

 

탐욕적 선택 속성

• 현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.
• 선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다.

 

최적 부분 구조

• 먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.