그리디 알고리즘?

• 눈 앞의 이익만을 추구하는 알고리즘.

• 실행시간이 빠르다.

• 대표적인 문제: 동전 문제

• 일반적으로 "최대한 적은", "최대한 많은" 이라는 문구가 문제에 들어가는 경우가 많다.
  -> 최대/최소의 경우의 수를 구할 것을 요구하는 문제들

• 그리디를 사용할 수 있는 조건이 주어진다

• 정렬을 한 뒤에 풀어야 하는 문제가 많다.

연습문제 BOJ 4796

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

문제: 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.
강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?
강산이는 조금 더 일반화해서 문제를 풀려고 한다.
캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

입력:
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

5 8 20
5 8 17
0 0 0

-> 캠핑장을 연속하는 8일 중 5일 사용할 수 있고, 강산이의 휴가는 20일
-> 20/8 = 2...4 -> 5*2 + 4 = 14

-> 캠핑장을 연속하는 8일 중 5일 사용할 수 있고, 강산이의 휴가는 17일
-> 17/8 = 2..1 -> 5*2 + 1 = 11

Case 1: 14
Case 2: 11

-> V/P = x..n -> L *x + n

//
//  main.cpp
//  4796
//
//  BOJ 4796 캠핑

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int L,P,V;
    int i = 1;
    while(1){
        cin >> L >> P >> V;
        if(L==0 && P==0 && V==0){
            break;
        }
        //V/P = x..n -> L *x + n
        cout << "Case " << i << ": "<< (V/P)*L + min(V%P, L) << endl;
        i++;
    }
    return 0;
}

BOJ 1931

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

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

예시 입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

• 그리디 알고리즘을 적용해보자.
  1) 종료시간이 가장 빠른 것을 선택
  2) 종료시간 이후 시작하는 것 중(current Time으로 설정) 가장 빨리 끝나는 것(종료 시간이 가장 빠른 것) 선택

-> 종료 시간을 기준으로 정렬해서,
(다음 회의) 시작시간 <= (이전 회의의) 종료시간 을 만족하는 회의를 선택

//
//  main.cpp
//  GreedySearch
//
//  BOJ 1931 회의실 배정

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    
    //인풋 아웃풋 시간 줄여주는
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    //N과 회의시간 입력받기
    int N;
    cin >> N;
    int a,b;
    
    vector<pair<int, int>> meetings;
    
    for(int i=0;i<N;i++){
        cin >> b >> a;
        meetings.push_back(make_pair(a,b));
    }
    //meetings vector에 시작시간, 끝 시간 삽입 -> 정렬
    sort(meetings.begin(), meetings.end());
    
    int current = meetings[0].first;
    int count = 1;
    
    for(int i = 1; i <= N ;i++){
        
        if(current <= meetings[i].second){
            count++;
            current = meetings[i].first;
        }
    }
    
    cout << count;
    
    return 0;
}

BOJ 11000

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

3
1 3
2 4
3 5

2

-그리디 알고리즘을 적용해보자🐢

• 얘도 최소의 강의실로 모든 수업을 가능하게 한다 -> '그리디'스러운 문제구나를 알 수 있음

위 예시로 이해해보자면,
총 3개의 수업을 하는데,
각 수업은 S ~ T 시간동안 진행되고,
1===3
2===4
3===5
요런식으로 진행된다.
그니까 첫번째 세번째 수업을 한 강의실에서, 두번째 수업은 다른 강의실에서 하면 되니까 총 2개의 강의실이 필요하다.

이것도 앞 문제와 비슷하게, 끝나는 시간을 기준으로 정렬해서 풀어보자.

//
//  main.cpp
//  11000
//
//  BOJ 11000 강의실 배정

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N;
    cin >> N;
    
    vector<pair<int, int>> classroom;
    int s,t;
    for(int i=0;i<N;i++){
        cin >> t >> s;
        //끝나는 시간, 시작 시간 순으로 저장
        classroom.push_back(make_pair(s,t));
    }
    //끝나는시간 기준으로 오름차순 정렬
    sort(classroom.begin(), classroom.end());
    
    //첫번째 수업 끝나는 시간 = current time
    int time = classroom[0].first;
    int cnt = 1;
    
    for(int i=1;i<=N;i++){
        if(time <= classroom[i].second){
            time = classroom[i].first;
            cnt++;
//            cout << i << time << cnt << endl;
        }
        
    }
    cout << cnt;
    
    return 0;
}

요렇게 했더니 반례가 돌아가지 않는다.

-> 바보여따. -> 같은 강의실에서 진행하는 최대 강의 수가 아니라
강의실!! 수를 구해야지

반례:
5
1 7
2 3
3 4
4 8
7 10

이걸 끝나는 시간을 기준으로 정렬하면
2 3
3 4
1 7
4 8
7 10
요런식
2-3, 3-4, 4-8 -> 1개
1-7, 7-10 -> 1개
=> 총 2개의 강의실을 사용

강의실 개수를 저장하는 리스트를 만들어서 그 길이를 출력하면 되지 않을까?
-> 우선순위 큐를 사용

//
//  main.cpp
//  11000
//
//  Created by 신정연 on 2023/06/21.
//  BOJ 11000 강의실 배정

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int N;
    cin >> N;
    
    vector<pair<int, int>> classroom;
    int s,t;
    for(int i=0;i<N;i++){
        cin >> t >> s;
        //끝나는 시간, 시작 시간 순으로 저장
        classroom.push_back(make_pair(s,t));
    }
    //끝나는시간 기준으로 오름차순 정렬
    sort(classroom.begin(), classroom.end());
    
    //강의실 queue 선언 -> rooms
    priority_queue<int, vector<int>, greater<int>> rooms;
    
    //첫번째 수업 끝나는 시간 = current time
    rooms.push(classroom[0].first);
    
    for(int i=1;i<N;i++){
        //같은 강의실에서 이어서 수업할 수 있으면
        if(rooms.top() <= classroom[i].second){
            rooms.pop();
        }
        rooms.push(classroom[i].first);
    }
    cout << rooms.size();
    
    return 0;
}

그래도 틀리뮤ㅠㅠ
반대로 시작시간을 기준으로 정렬해서 반대로 코드를 썼더니 맞아따
왜지..

//
//  main.cpp
//  11000
//
//  Created by 신정연 on 2023/06/21.
//  BOJ 11000 강의실 배정

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int N;
    cin >> N;
    
    vector<pair<int, int>> classroom;
    int s,t;
    for(int i=0;i<N;i++){
        cin >> s >> t;
        classroom.push_back(make_pair(s,t));
    }
    //끝나는시간 기준으로 오름차순 정렬
    sort(classroom.begin(), classroom.end());
    
    //강의실 queue 선언 -> rooms
    priority_queue<int, vector<int>, greater<int>> rooms;
    
    //첫번째 수업 끝나는 시간 = current time
    rooms.push(classroom[0].second);
    
    for(int i=1;i<N;i++){
        //같은 강의실에서 이어서 수업할 수 있으면
        if(rooms.top() <= classroom[i].first){
            rooms.pop();
        }
        rooms.push(classroom[i].second);
    }
    cout << rooms.size();
    
    return 0;
}

🍏 reference
https://sectumsempra.tistory.com/88