💎 문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
💎 입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
ex)
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
💎 출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
ex)
4
💎 풀이 방법
그리디 알고리즘의 가장 기본적인 문제 중 하나인 시간에 따라서 회의실을 배정해주는 문제이다. 그리디 알고리즘을 이용하기 위해서는 greedy 즉 탐욕스러운 이라는 뜻을 직역한 그대로 그 순간에 해당하는 최적의 선택만을 해나가는 알고리즘이다. 따라서 주로 하나의 결과를 만들기 위해 이에 해당하는 여러가지 선택을 골라야 하는 문제에서 주로 많이 적용시킬 수 있다.(거스름돈, 회의실 배정, 배낭에 짐싣는 문제 등)
문제점은 이러한 그리디 알고리즘은 항상 최선의 선택을 할 수 는 없다는 것이다. 그 순간에서의 최적의 선택을 하기 때문에 경로를 되돌아갈 수 없고 이 때 전체적인 측면에서는 최적의 선택을 하지 못할 수도 있기 때문이다. 이러한 이유로 그리디 알고리즘을 사용하는 경우는 두 가지 조건이 만족되어야하며 이는
1. Greedy Choice Property(탐욕적 선택 속성)
2. Optimal Substructure(최적 부분 구조)
위 두가지 내용을 만족하여야한다. 전자는 앞의 선택이 이후의 영향을 주지 않도록 반드시 전체적인 측면에서 최적의 해가 나올 수 있어야 하는 것이며, 후자는 전체적인 측면 이외에 부분적으로 해를 구할 경우에도 최적의 해결방법이어야 한다는 것이다.
이러한!! 그리디 알고리즘의 특성을 잘 이용한 회의실 배정 문제를 적용시켜서 풀어보았다. 회의실에 시간을 저장해주기 위해서 vector에 pair을 넣어서 시작시간과 끝시간을 vector에 저장시켜주었다.
cin >> N;
vector <pair <int, int>> v(N);
for(int i = 0;i < N;i++){
int start, end;
cin >> start >> end;
v[i] = make_pair(start, end);
}이러한 회의실의 시간이 담긴 vector를 이용하여 최적의 회의실 사용표를 구성해준 뒤 몇 개의 회의실을 사용할 수 있을지 구하면된다. 이 때 최적이 되기 위해서, 그리고 전체적으로 어떻게 해야 최적인 사용을 할 수 있을지 고민하는 것이 중요하다. 회의실을 많이 쓰려면 최대한 촘촘한 시간 구성이 필요하고 이에 따라 회의실 사용을 마친 시간이 빠른 순으로 정렬한다면 종료시간과 다음 회의실 시작 시간을 비교하여 최적의 회의실 사용표를 구성할 수 있을 것이다. 이르게 회의실을 마칠수록 다른 회의실을 사용할 수 있는 기회가 많기 때문에 이러한 생각을 하였고 앞서 소개한 그리디 알고리즘의 두 조건에서 위배되는 것없이 전체적, 부분적으로 보았을 때 항상 최적의 선택을 할 수 있을 것이다.
sort(v.begin(), v.end());
sort(v.begin(), v.end(), cmp);
int end = v[0].second;
while(count != N){
if(count == 0)
result++;
else{
if(end <= v[count].first){
end = v[count].second;
result++;
}
}
count++;
}여기서 주의해야할 점은!! 시작시간을 먼저 정렬해준 뒤 마치는 시간을 다음에 정렬해야한다는 점이다!! 만약 종료시간을 기준으로 vector을 정렬해준다면 7 7, 3 7과 같은 끝나는 시간이 같은 회의실들 중 시작 시간과 종료 시간이 같은 회의실의 순서에서 최적의 선택을 하지 못할 수 있기 때문에 주의하여야 한다. 이 이후는 회의실의 개수들에 따라 반복하면서 최대 몇 개의 회의실을 사용할 수 있을지 선택한 회의실의 종료시간과 다음으로 사용할 회의실의 시작시간을 비교해가면서 골라준다!!
문제의 예제 테스트케이스를 구현해보면 위 그림과 같다. 종료시간에 따라 정렬해준 뒤 이를 처음부터 종료시간과 다음 회의실 시작시간을 비교해주면서 차례로 계산해보면서 회의실의 최대 갯수를 구해준다!!
💎 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.second < b.second;
}
int main(int argc, const char * argv[]) {
int result = 0;
int count = 0;
cin >> N;
vector <pair <int, int>> v(N);
for(int i = 0;i < N;i++){
int start, end;
cin >> start >> end;
v[i] = make_pair(start, end);
}
sort(v.begin(), v.end());
sort(v.begin(), v.end(), cmp);
int end = v[0].second;
while(count != N){
if(count == 0)
result++;
else{
if(end <= v[count].first){
end = v[count].second;
result++;
}
}
count++;
}
cout << result << "\n";
return 0;
}
💎 고민
그리디 알고리즘을 이용하여 문제를 풀어보았다!! 가장 기초적인 알고리즘을 주로 풀어보면서 블로그에 글을 게시해보고 있는데 벌써 방학한지 한달이 지나있더라,,,최대한 꾸준히 알고리즘은 올리도록 노력해보고 있었는데 정보처리기사나 flutter, 리액트와 같은 다른 내용들의 게시글도 써보고 싶은데 여유되는 대로 소개해보고 싶다!!
그리디 알고리즘은 위에서 소개한대로 2가지 조건을 명심하면서 적용시키는 방법을 고민해보도록 하자. 전체적인 측면에서 최적인지, 부분적으로 최적인 경우를 탐색하는지 이를 잘 고민해보고 구현할 수 있도록 하자!! 다음 문제도 그리디 알고리즘을 풀 수 있으면 풀어보도록 하겠다!!
화팅!!
