그리디

현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘

• 항상 최적의 해를 보장하지는 못한다.

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
   • 전체 문제를 해결하지 못한다면, 1로 돌아가 같은 과정을 반복

주로 우선 순위 큐를 활용해서 구현.

#include <queue>

priority_queue<int> pq1; // 내림차순 정렬
priority_queue<int,vector<int>,greater<int>> pq2; // 오름차순 정렬