1. 정의
매 순간 최적의 해를 선택해나가며 결국 전체 최적해를 구하는 풀이 전략
2. 그리디 알고리즘 활용 조건
그리디 알고리즘을 활용하려면, 선택에 순서가 존재해야 한다. 즉 매 시점마다 고를 수 있는 것과 고를 수 없는 것이 구분되어야 하며, 출발점과 끝점이 존재해야 한다.
위는 일자 별로 강의를 하나씩 고를 수 있을 때, 최대 비용을 고르는 문제이다.
선택에는 날짜라는 순서가 존재한다. 또한 강의는 시간이 지날 때마다 고를 수 있는 강의와 그렇지 않은 강의로 나뉜다. 이러한 문제는 맨 마지막 일자부터 첫 일자로 거꾸로 오며 그떄의 최대 비용 강의를 고르면 되는 문제이다.
선택에는 날짜라는 순서가 존재한다. 또한 강의는 시간이 지날 때마다 고를 수 있는 강의와 그렇지 않은 강의로 나뉜다. 이러한 문제는 맨 마지막 일자부터 첫 일자로 거꾸로 오며 그떄의 최대 비용 강의를 고르면 되는 문제이다.
TIP: 문제에서 순서가 주어지지 않았다면, 정렬을 사용해 순서를 만든다.그리디 알고리즘 문제인지 확인하고 싶다면, 정렬을 해서
출발점과 끝점, 매 시점마다 선택할 수 있는 것과 없는 것이 구분되어 존재하는지 를 확인하면 된다.⬅️ 이전 글