8. 그리디

그리디

빠른 설명

그리디는 매 순간 가장 좋아 보이는 선택을 하는 알고리즘이다. 단, 그 선택이 전체 최적해로 이어진다는 근거가 있어야 한다.

언제 쓰는가

• 정렬 후 앞에서부터 선택하는 문제
• 회의실 배정, 동전, 구간 선택처럼 지역 선택이 전체 선택으로 이어지는 문제
• “최소”, “최대”가 나오지만 DP까지는 필요 없어 보이는 문제

시간복잡도

• 정렬이 필요하면 보통 $O(N\log N)$
• 정렬 뒤 한 번 훑으면 $O(N)$

참고자료

• Wikipedia - Greedy algorithm
• USACO Guide - Greedy
• GeeksforGeeks - Greedy Algorithms

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<pair<int, int>> meetings = {{1, 4}, {2, 3}, {3, 5}, {6, 8}};
 
    sort(meetings.begin(), meetings.end(), [](auto a, auto b) {
        return a.second < b.second;
    });
 
    int count = 0;
    int last_end = -1;
    for (auto [start, end] : meetings) {
        if (start >= last_end) {
            count++;
            last_end = end;
        }
    }
 
    cout << count << '\n';
}

Python 코드

meetings = [(1, 4), (2, 3), (3, 5), (6, 8)]
meetings.sort(key=lambda x: x[1])
 
count = 0
last_end = -1
for start, end in meetings:
    if start >= last_end:
        count += 1
        last_end = end
 
print(count)