c++ - 11주차

<그리디 알고리즘>

그리지 알고리즘 - 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

수행과정

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제 해결 못하면 다시 1. 으로 돌아감

 

 

 

 

 

예제 ) 1931. 회의실 배정

#include <bits/stdc++.h>

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; // 음수로 두는 이유는 자연수 또는 0 이라고 했기 때문


	for (int i = 0; i < N; i++)
	{
		if (A[i].second >= end)
		{
			end = A[i].first;
			count++;

		}



	}
	cout << count;


	return 0;
}