섹션 4. 탐욕 알고리즘(Greedy Algorithm)

그리디 알고리즘

그리디(greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지중 최선의 선택지라고 가졍하는 알고리즘이다.

 

최적의 해를 보장하지는 않는다.

 

그리디 알고리즘 수행 과정

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

ex) 회의실 배정하기 (백준 1931)

1. 문제 분석하기
   1. 가장 많이 진행하려면
   2. 회의가 겹치치 않게 최대한 많은 회의를 배정 → 그리디 알고리즘
   3. 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는게 유리
   4. 종료 시간이 빠른 순서대로 정렬
   5. 정렬 시, 시작하자마자 끝나는 반례 주의
      1. 종료 시간이 같을 때는 시작 시간을 기준으로 다시 정렬
      2. 차례대로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<pair<int, int>> a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i].second;
		cin >> a[i].first;
	}

	sort(a.begin(), a.end());

	int count = 0;
	int end = -1;

	for (int i = 0; i < n; i++) {
		if (a[i].second >= end) {
			end = a[i].first;
			count++;
		}
	}
	cout << count << "\n";
}