그리디 알고리즘

그리디 예시 : 지폐문제

가장 흔한 그리디 문제인 지폐문제

 

10000원 5장

5000원 5장

1000원 5장

100원 5장

 

이 있을 때 12100을 내기위해 가장 적은 갯수의 돈을 내는 최적해는?

-> 가장 큰 지폐부터 순서대로 계산하면 된다.

 

그런데 

8000원 5장

5000원 5장

1000원 5장

100원 5장 

 

인 경우에 가장 큰것부터하면

8000원 1개

1000원 4개

100원 1개 

 

라서

5000원 2개

1000원 2개

100원 1개

의 경우의 수보다 크다.

 

따라서 언제나 큰게 최적해는 아니다.

 

증명

해당 명제에 대해 탐욕 선택 충족이 되는 해를 찾아야한다.

 

그렇다면 그 선택이 해당 명제에 최적이라는 건 어떻게 알 수 있을 까?

증명을 통해서 확인하면 된다. 

 

직접 증명

 명제 : n은 짝수다

 직접 증명 : n % 2 는 0이다.

 

간접 증명

직접증명이 힘든 경우에는 간접 증명을 사용한다.

간접증명 : 귀류법

어떤 명제가 거짓이다. 라고 가정을 하고, 거짓이라고 한 가정이 거짓임을 밝혀내는 방법.

 

루트2는 무리수이다 는건 직접 증명하기 힘들다.

루트2는 유리수이다 라고 거짓 명제를 만들고,

유리수라면 a / b 로 나타낼 수 있다. a 와 b는 정수인 서로소이다.

 

루트 2 = a / b 

2 = a^2 / b^2

2 x b^2 = a^2

좌항은 짝수이기 때문에 우항도 짝수이다.

그러나 서로소인 경우에는 양쪽이 다 짝수일 수는 없다.

 

문제를 푸는 방법

1. 일단 브루트 포스로 해본다.

2. DP로 풀어본다

3. 그리드로 풀어본다 (최종적으로!)

4. 참고로 그리디는 정렬이나 우선순위 큐 혹은 둘다 쓰면 풀리는 경우가 많다.

 

그리디 구간문제

구간이 주어지는 문제들은 반드시 정렬이 선행되야 한다.

그러나 어떤 것을 기준으로 정렬할지를 생각해야하는데,

잘 모르겠으면 하나씩 다 돌려보고 테스트 케이스를 통과하는 것으로 결정해도 무방하다.

 

구간이 주어지고, 가장 많이 실행하는 횟수 문제는

end 시간으로 정렬하고 순서대로 실행하면 된다!

 

최악 제거하기

그리디는 최대를 만드는건데

최대를 극대화 하거나 최악을 제거하면 최대가 된다.

https://www.acmicpc.net/problem/2109

 

 

날짜 기준으로 정렬한 다음

pq에 price만 넣으면서 넣을 때마다 갯수를 넘었으면 '최악(제일 싼 것)'을 팝으로 제거한다

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

    int n, d, pay;
    cin >> n;

    // greater를 최대힙. 제일 낮은 값이 위로 올라감
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> pay >> d;
        v[i] = { d, pay };
    }

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

    for (int i = 0; i < n; ++i)
    {
        pq.push(v[i].second);

        // 매번 넣을 때마다 최악(젤 싼거)을 삭제
        if (pq.size() > v[i].first)
            pq.pop();
    }

    int ret = 0;
    while (pq.size())
    {
        ret += pq.top();
        pq.pop();
    }

    cout << ret;
}