[Algorithm] Greedy Algorithm

Updated: July 14, 2021

문제: 주어진 상황에서 최대한 많이 할 수 있는 Activity 수와 종류를 구해보자.
조건
- 각 활동들은 시작시간과 종료시간이 주어져 있음.
- 한 Activity가 종료되어야 다른 Activity를 시작할 수 있음.
문제 예시
- 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 문제
- 10원, 50원, 100원이 있을 때 최소 동전으로 교환하는 문제
- 문자열 합치기(문자열들의 길이가 주어지고, 한 줄에 모든 문자열을 합칠 때 필요한 최소비용을 출력하는 문제)
문제 해결 접근 방법
1. 가장 먼저 end[]를 기준으로 오름차순 정렬(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬함)
2. 첫 번째 활동은 가장 먼저 끝나는 것을 선택하는 것이 현재 단계에서의 가장 최선의 선택 : 가장 먼저 시작하는 ‘D’를 선택
3. 첫 번째 활동이 끝난 시점에서 가장 먼저 끝낼 수 있을 다음 활동을 찾음 : ‘E’를 선택함.
4. 모든 활동을 탐색할 때 까지 3의 과정을 반복함.