[Algorithm] Greedy(탐욕) 알고리즘

🚦 이번 포스팅에서는 〰️

▶️ Greedy(탐욕) 알고리즘이란?
▶️ Greedy(탐욕) 알고리즘 문제 풀어보기

 

📌 Greedy(탐욕) 알고리즘이란?

---

: 각 단계에서 가장 최선의 선택을 하는 기법이다.

• 현재의 선택이 나중에 미칠 영향을 고려하지 않는다.
• 그렇기 때문에, 그 정당성 분석이 중요하다.
  ▶️ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요!
• 동적(dynamic) 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위한 개념이다.
• 대표적인 문제로 거스름돈 문제, 활동 선택 문제 등이 있다.

 

 

 

 

📌 Greedy(탐욕) 알고리즘 문제 풀어보기

---

1️⃣ 백준 14916 거스름돈

 

동전의 개수가 최소가 되도록 거슬러줘야 하기 때문에 되도록 큰 단위의 동전을 많이 거슬러 주는 그리디 알고리즘을 사용한다.

dp로도 풀 수 있지만 여기선 그리디로 풀어보자.

 

#include <iostream>
using namespace std;

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

    int N; cin >> N;

    int cnt = N / 5;
    int rest = N % 5;
    if(cnt > 0 && rest%2 != 0) {
        rest += 5;
        cnt--;
    }
    
    if(rest%2 == 0) cout << cnt + rest/2 << '\n';
    else cout << -1 << '\n';

    return 0;
}

 

 

1. 동전을 일단 제일 큰 5 단위로 나눈다.
2. 만약 동전을 5로 나눴고 그 나머지가 2로 나눠지지 않는다면, 나머지에 5를 한번 더해주고 count를 하나 감소시킨다.
3. 나머지가 2로 나눠진다면 그 값을 더해서 출력한다.
4. 나머지가 2로 나눠지지 않는다면 (애초에 N < 1) -1를 출력한다.

 

 

2️⃣ 백준 11000 강의실 배정

 

 

[풀이 과정]

1. 강의 시간표를 시작 시간 순서대로 정렬한다.
2. 첫번째 순서의 끝나는 시간을 큐에 저장해준다.
3. 두번째 강의부터 강의 시작시간이 큐에 있는 시간보다 크거나 같다면 같은 강의실을 써도 되므로 큐에 있던 끝나는 시간을 바꿔준다. (pop and push)
4. 만약 그렇지 않다면 강의실이 한개 더 필요하므로 끝나는 시간을 큐에 넣어준다.
5. 모든 연산을 다 마쳤을 때 큐의 크기가 필요한 강의실의 개수이다.

 

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

/* pseudo code
for a in max time
    if class a.start time >= max time
        change max time to a.end time
    else
        plus max time
*/
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    priority_queue<int, vector<int>, greater<int> > classes;

    int N; cin >> N;
    vector<pair<int, int> > temp;


    for(int i=0; i<N; i++){
        int s,t; cin >> s >> t;
        temp.push_back(make_pair(s,t));
    }
    sort(temp.begin(), temp.end());
    classes.push(temp[0].second);

    for(int i=1; i<N; i++)
    {
        if(temp[i].first >= classes.top()) {
            classes.pop();
            classes.push(temp[i].second);
        }
        else classes.push(temp[i].second);
    }
    cout << classes.size() << '\n';

    return 0;
}

 

 

[Reference]

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188