그리디 (Greedy)

그리디 알고리즘은 지역적 최적해들을 찾아서 전역적 최적해를 구하는 방식입니다.

즉, 그 순간에 '탐욕적으로' 최선이라 생각하는 선택지들을 골라, 최종적으로 최선인 정답을 도출해내는 방법이죠.

 

참고로, 보통 문제 풀이에서 다음의 과정을 거치곤 합니다.

무식하게 풀기 -> DP -> 그리디 

 

즉 보통 그리디는 최후의 최후에 사용하곤 합니다.

또한, DP로 풀이할 수 있는 것들은 대부분 그리디로도 풀이할 수 있긴 합니다.

오직 그리디로만 풀리는 문제는 DP의 메모이제이션 용량이 너~무 커서 DP를 사용할 수 없는 경우입니다.

 

그리디가 성립하기 위한 조건

1. 최적 부분 구조

전체 문제를 작은 부분 문제로 나눌 수 있어야하며, 그 작은 부분 문제의 최적해들을 모아 전체 문제의 최적해를 이룰 수 있는 구조를 의미합니다.

2. 탐욕 선택 속성

각 단계(작은 단계)에서의 최적 선택이 전체 문제에 대해서도 최적의 해를 보장한다는 것을 의미합니다.

---

 

따라서 1. 최적 부분 구조와 2. 탐욕 선택 속성이 동시에 만족되어야만 그리디로 문제를 풀어낼 수 있습니다.

여기서 중요한 부분은 보통 2번 조건 입니다. 1번 조건은 보통 대부분 만족할 수 있으나, 2번 조건은 만족하는지 알려면 증명해봐야합니다.

 

탐욕 선택 속성을 만족하는지 파악하는 방법 

1. 직접 증명

해당 명제가 참임을 '직접' 증명하는 방식입니다. 즉, 증명하려는 명제가 참이라는 것을 논리적인 순서에 따라 증명하는 방법입니다.

ex) 짝수의 합은 짝수다 를 증명하기 위해 직접 증명을 사용하곤 합니다.

 

2. 간접 증명( 中 귀류법)

간접 증명은 말 그대로 간접적으로 증명하는 방식입니다. 그 중에서 귀류법이라는 증명 방식이 가장 유명합니다.

귀류법은 해당 명제를 거짓이라고 가정하고, 그 가정이 모순됨을 보임으로써 본 명제가 참임을 증명하는 방식입니다.

ex) 루트2는 무리수다 를 증명하기 위해 귀류법을 사용하곤 합니다. 

 

예를 들어, "1 + 1 은 2다." 라는 명제를 증명하기 위해

"1 + 1은 2가 아니다" 가 참이라고 생각하고, 이를 증명해나가면서 모순점을 발굴하는 방식입니다.

 

하지만 정석적인 알고리즘이 아닌, 코딩테스트에서는 위의 증명 과정을 거칠 시간이 없습니다.

 

코딩테스트에서 그리디를 적용하는 방법

1. 어떤 명제를 생각해낸다. (~~를 하기 위해서 탐욕적으로 ~~를 하면 최적이지 않을까?)

2. 코드로 구현해보고 테스트한다. (테스트 케이스 통과하는지 돌려보거나 생각해본다)

3. 만약 틀렸다면 명제를 고치고 다시 구현한다.

 

이렇게 1~3번의 과정을 빠르게 진행하는게 좋습니다. 

즉 빠르게 시도해보고, 빠르게 좌절하고, 다시 시도하는 꺾이지 않는 마음이 중요합니다.

 

그리디 알고리즘 자체가 틀릴 가능성이 높은 알고리즘이니, 빠르게 다른 방식으로 해보면서 결국 정답을 찾아가는게 중요합니다.

그래서 최후의 수단이라고도 표현했습니다. 틀릴 가능성이 높으니까요. 

 

 

그리디를 구축하는데 보통 쓰이는 방법

1. 정렬 (sort)

2. 우선순위 큐 (priority queue)

 

보통 위의 2가지 방식이 혼합되어 구현되는 경우가 많습니다. 

예시 문제를 풀어보다보면 더욱 느껴질겁니다. 

 

 

그리디 연습 문제

문제 1. 

민수는 도서관의 사서입니다.
도서관에는 학생들이 자유롭게 사용할 수 있는 단 하나의 좌석이 있습니다.
학생들은 특정한 시간에 도착해 일정 시간 동안 좌석을 사용한 뒤 떠납니다.

민수는 가능한 한 많은 학생들이 좌석을 사용할 수 있도록 조정하려고 합니다.
최대로 좌석을 사용할 수 있는 학생 수를 구하세요.

• 입력
  • 첫 줄: 학생 수 N (1 ≤ N ≤ 100,000)
  • 다음 N줄: 각 학생의 도착 시간, 떠나는 시간
• 출력
  • 최대 몇 명의 학생이 좌석을 사용할 수 있는지 출력

📊 예제 입력 / 출력

 

예제 1

5
1 4
2 5
3 6
5 7
8 9

3

 

 

예제 2

7
1 4
2 3
3 5
4 6
5 7
7 8
8 9

5

 

해당 문제를 만약 무식하게 푼다면, 어떤 학생이 포함되거나 포함되지 않는 경우를 생각해보면 간단합니다.
즉 모든 조합 중에서, 가장 많은 학생을 포함하는 조합을 찾으면 됩니다. 하지만 해당 방식은 O(2^N)의 시간 복잡도를 가집니다.

따라서 해당 문제를 그리디로 풀어봅시다. (물론 DP로도 풀 수 있긴 합니다.)
우선 방식을 여러개를 생각해봅니다.

1. 도착 시간을 기준으로 오름차순 정렬
2. 떠나는 시간을 기준으로 오름차순 정렬
3. 사용하는 기간(떠나는시간 - 도착시간)을 기준으로 오름차순 정렬
... (내림 차순으로 해본다던지 등등)

1번 방식을 우선 구현해보면, 예제 2를 통과하지 못합니다. 그럼 버립니다.
2번 방식으로 구현해봅니다. -> 테스트케이스를 다 통과했다? -> 되는구나 -> 제출

 

 

정답 코드 

#include <bits/stdc++.h>
using namespace std;

int from, to, n, ret = 1;

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

    cin >> n;
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        cin >> from >> to;
        v.push_back({to, from}); // (끝나는 시간, 시작 시간)
    }

    sort(v.begin(), v.end()); // 끝나는 시간 기준 정렬
    int last_end = v[0].first;

    for(int i = 1; i < n; i++){
        if(v[i].second < last_end) continue; // 겹치면 패스
        last_end = v[i].first;
        ret++;
    }

    cout << ret << '\n';
    return 0;
}

 

---

 

문제 2.

동훈은 N개의 골동품과 K개의 가방을 가지고 있습니다.

• 각 골동품은 무게 M[i], 가치 V[i]를 가짐
• 각 가방은 무게 제한 C[i]를 가짐
• 한 가방에는 골동품 1개만 담을 수 있음

최대로 얻을 수 있는 골동품 가치의 합을 구하라.

 

• 입력
  • 첫째 줄에 골동품의 수 N과 가방의 수 K가 주어집니다. (1 ≤ N,K ≤ 300,000)
  • 다음 N줄 :  각 골동품의 정보(M[i], V[i])가 주어집니다. (0 ≤M[i], V[i]≤1,000,000)
  • 다음 K줄 : 가방에 담을 수 있는 최대 무게 C[i]가 주어집니다. (1 ≤ C[i] ≤100,000,000)

 

• 출력
  • 동훈이 수집할 수 있는 골동품 가치의 합의 최대값을 출력

 

 

📊 예제 입력 / 출력

예제 1

4 2
1 100
2 200
11 400
10 500
10
11

900

 

 

예제 2

7 4
3 30
4 35
5 40
6 60
10 100
7 90
8 85
9
5
4
15

265

 

해당 문제도 무식하게 풀려다가 생각해보면 N, K 가 꽤 큰 걸 볼 수 있습니다. 따라서 그리디로 풀어봅시다.
단순하게 다음과 같은 방법을 우선 생각해볼 수 있습니다.

1. 가방의 크기를 내림차순으로 정렬하고, 골동품의 가치가 높은 것부터 차례대로 담아본다.
2. 가방의 크기를 오름차순으로 정렬하고, 골동품의 가치가 높은 것부터 차례 대로 담아본다.
...

해당 명제들을 새우고 빠르게 진행해도 되지만 조금만 더 생각을 해봅시다.

결국 수집할 수 있는 골동품의 가치가 최대가 되기 위해서는, 
가능한 작은 가방에, 높은 가치를 넣는게 좋지 않을까요? 그게 가성비니까요.

 

정답 코드

//그리디, 정렬, 우선순위 큐
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, k, ret;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    vector<pair<ll,ll>> v(n); // (무게, 가치)
    vector<ll> bags(k);

    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    for(int i = 0; i < k; i++) cin >> bags[i];

    sort(v.begin(), v.end());     // 골동품: 무게 오름차순
    sort(bags.begin(), bags.end()); // 가방: 무게 오름차순

    priority_queue<ll> pq;
    int j = 0;

    for(int i = 0; i < k; i++){
        while(j < n && v[j].first <= bags[i]){
            pq.push(v[j].second); // 가방에 담을 수 있는 골동품 추가
            j++;
        }
        if(!pq.empty()){
            ret += pq.top(); // 가장 가치 큰 골동품 선택
            pq.pop();
        }
    }

    cout << ret << "\n";
    return 0;
}

 

위의 코드는 결국 오름차순으로 가방을 정렬해서, 담을 수 있는 골동품을 하나 하나 담아보는 코드입니다.

그리고 우선순위 큐에 의해, 가장 큰 value(가치)를 가진 값을 가져와서 최종적으로 해당 가방에 넣는 코드입니다.

우선순위 큐와, 정렬 모두 활용했네요.

 

---

문제 3.

큰돌 교수님은 학생들의 성적을 분석하여
성적이 낮은 5명의 학생을 뽑아 추가 지도를 하려고 합니다.

• 학생 수 N (6 ≤ N ≤ 50,000,000)
• 학생 성적은 0 ~ 100 (소수점 2자리, 0.01 단위 가능)

성적이 낮은 5명을 오름차순으로 출력하세요.

 

• 입력
  • 첫째 줄에 학생의 수 N이 주어집니다. (6 ≤ N ≤ 50,000,000)
  • 둘째 줄부터 N개의 줄에 학생들의 성적이 무작위로 주어집니다. (0~100, 0.01점 단위로 부여)

• 출력
  • 성적이 좋지 않은 5명의 학생의 성적을 낮은 순서대로 각 줄마다 출력. 동점자가 있을 경우에도 5명만 출력.

📊 예제 입력 / 출력

예제 1

8
95.6
74.3
88.2
53.1
92.7
67.9
88.2
45.5

45.5
53.1
67.9
74.3
88.2

 

예제 2

10
34.5
56.7
78.9
34.5
12.3
90.1
23.4
67.8
12.3
89.9

12.3
12.3
23.4
34.5
34.5

 

 

이번 문제는 사실 정렬하면 풀리는 문제지만, N이 너무 커서 메모리 초과가 납니다. (보통 3000만 정도까지만 가능)
따라서 메모리 관리를 잘해주는게 핵심인데, 이 문제는 우선 순위 큐를 활용해야합니다. 

우선 순위 큐에 넣으면 자동으로 높은 값을 맨 위로 올려주기 때문에 따로 정렬할 필요는 없습니다. (삽입 시에 그 대가를 지불)
따라서 우선 순위 큐의 크기가 5를 넘는 순간, pop만 잘해주어 공간 복잡도를 초과하지 않게 만들면 됩니다.

그리디 문제로 볼 수도 있지만 우선 순위 큐를 사용할 줄 아는지에 더욱 포커싱 되어 있는 문제입니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int n;
double temp;
priority_queue<double> pq; 
vector<double> v;

int main () {
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%lf", &temp);
        if(pq.size() == 5){
            pq.push(temp);
            pq.pop(); // 가장 큰 값 제거
        } else {
            pq.push(temp);
        }
    }
    while(!pq.empty()){
        v.push_back(pq.top());
        pq.pop();
    }
    reverse(v.begin(), v.end()); // 오름차순 출력
    for(double i : v) printf("%.2lf\n", i);
    return 0;
}