[greedy] 회의실 배정 (백준 1931번)

그리디 알고리즘 (탐욕 알고리즘)이라고 하는데, 비슷한 종류의 문제들 중에 이게 가장 수준이 높았던 거 같다.

그리디 알고리즘은, 솔직히 나는 이런 거에 알고리즘이라는 말을 붙일 필요가 있나 싶을 정도로 간단했다.

그 순간 순간의 최적해를 쫓아 가서, 근사값을 구하는 방식의 알고리즘이라는 건데,

당연 그 순간의 최적해를 쫓을 때 최종적인 답안이 최적해가 아닐 수도 있다.

말하자면, 지금 알고리즘 조건에 따라서,

이렇게 설명할 수 있겠다.

2일 간격으로만 음식을 먹을 수 있고, 더 적은 음식을 먹어야할 때, 첫날 음식을 먹느냐 둘째날 음식을 먹느냐,

첫날과 둘째날을 비교해서 작은 쪽을 먹는다는 게 그리디의 방식이지만,

만약 셋째날이 무한대에 수렴한다면 다시 처음으로 돌아가 두번째를 먹는 것을 고르는 것이 옳다.

 

그래서 greedy 방식은 내 생각엔,

첫째, 근사값을 구해도 상관없다, 어느 정도 오차범위는 인정한다는 생각일 때 또는

둘째, 근사값을 구해 나가는 것이 정답이 도출될거란 확신이 있을 때

이 두 경우에만 사용하는 것이 옳을 듯 한데,

이 두번째 경우의 대표적인 예시가 데이터가 정렬되어 있는 경우를 의미할 것이다.

 

그렇게 따지면 정렬 후 그리디 알고리즘을 사용하는 것은

복잡한 알고리즘, 예컨대 dfs, bfs처럼 탐색을 진행하는 것보다 효율적일 수 있겠다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
vector <pair <int, int>> meeting;
 
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int start, end;
        cin >> start >> end;
 
        meeting.push_back(make_pair(end, start));
        // 잘 보면 알겠지만, 첫번째 인자를 end로 주었다 (끝나는 시간.)
    }
    sort(meeting.begin(), meeting.end());
 
//    for (int i = 0; i < meeting.size(); i++)
//    {
//        cout << meeting[i].first << ' ' << meeting[i].second << endl;
//    }
//  끝나는 시간이 빠른 순서로 출력되는지 확인하기 위해서 만들어본 식이다.
 
    int startTime = 0; // startTime은 다음 번에 시작할 수 있는 시간, 즉 전에 끝난 시간이다.
    int counted = 0;
 
    for (int i = 0; i < meeting.size(); i++)
    {
        int nextStart = meeting[i].second;
        int nextEnd = meeting[i].first;
 
        if (startTime <= nextStart)
        {
            startTime = nextEnd;
            counted++;
        }
    }
 
    cout << counted;
}
// greed는 특정 상황에서만 작동하는 알고리즘을 말하는데,
// 까놓고 말해서 이 특정 상황이라는 게 정렬된 상황을 말하는 게 대부분인 듯하다.