1. 개념

문제 해결의 각 단계에서 매 순간에 최선이라고 생각되는 선택을 해서 전체 문제에 대한 최적의 해를 구하는 알고리즘

즉, 지역적 최적해를 모아서 전역적 최적해를 구하는 방식이다.

2. 접근 순서

구현 -> 완전 탐색(브루트포스) -> DP -> 그리디 순서로 접근하기

3. 그리디 풀이 순서

1. 전역 문제와 지역 문제를 인식한다
2. '이 문제는 매 순간 ~를 하면 답을 찾을 수 있을 것이다`라고 명제를 떠올리기
3. 해당 명제를 기반으로 테스트케이스가 통과하는지 확인
4. 시간복잡도 확인 및 코드 구현
5. 반례있으면 빠르게 새로운 명제로 다시 시도해보기 (우디르급 태세 전환이 필요하다)

4. 그리디 알고리즘의 구현

(1) 정렬 -> sort(), priority_queue<자료형>

그리디 알고리즘은 거의 대부분 정렬을 사용해서 구현한다.

sort()

sort(a.begin(), a.end()) -> 오름 차순 정렬
sort(a.begin(), a.end(), cmp) -> cmp에 따라 정렬

• 시간복잡도 : O(nlogn)

priority_queue

priority_queue<int> pq1; -> 내림차순의 우선순위 큐 생성
priority_queue<int, vector<int>, greater<int>> pq2; -> 오름차순의 우선순위 큐 생성 

• 시간복잡도
  • 삽입: O(logN)
  • 삭제: O(logN)
  • 최댓값 조회: O(1)

5. 예시

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, ret, temp1, temp;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	vector<pair<ll,ll>> v(n);
	vector<ll> vv(k);
	for(int i = 0; i < n; i++){
	cin >> v[i].first >> v[i].second;
	}
	for(int i = 0; i < k; i++) cin >> vv[i];
	sort(v.begin(), v.end());
	sort(vv.begin(), vv.end());
	priority_queue<ll> pq;
	int j = 0;
	for(int i = 0; i < k; i++){
		while(j < n && v[j].first <= vv[i]) pq.push(v[j++].second);
		if(pq.size()){
			ret += pq.top(); pq.pop();
		}
	}
	cout << ret << "\n";
	return 0;
}