그리디 알고리즘 Greedy Algorithm C++

개요

1. 문제를 풀이할 기준을 세운다.
2. Greedy Choice Property : 세운 기준이 변경되면 안된다.
3. Optimal Substructure(부분 최적해) : 수립한 기준을 검증할 수 있어야 한다.

부분 최적해를 통해 앞서 계산된 결과를 다른 부분에서도 그대로 가져가서 쓸 수 있다면 그리디 알고리즘이 성립된다.

그리디 알고리즘은 수학적으로 검증이 가능하다.

 

예제

1. ATM 문제

ATM이 1대가 있을때 A, B, C 인원 세명이 ATM을 이용하려고 한다. ATM 이용 시간은 각자 A = 30분, B = 20분, C = 5분 이라고 가정할때 이때 총 걸리는 대기 시간은?

1. 문제 인식 : 대기 인원수는 ATM을 사용할 수록 줄어들고, 대기 시간은 점점 늘어난다.

2. 기준 수립 : ATM 이용 시간이 적은 순서대로 ATM을 사용하면 총 대기 시간이 최소가 된다.

3. 부분 최적해 : C > B > A 순으로 ATM을 사용해 본 후 해당 방식이 총 대기 시간이 가장 적다는걸 검증한다.

 

2. 회의실 배정

회의실은 1개만 존재하고 여러개의 회의실 예약의 입력이 주어졌을 때 가장 많은 회의를 열리게 하고 싶은 경우 총 회의의 개수는?

1. 문제 인식 : 회의실 시간이 겹칠 경우 다른 팀은 이용하지 못한다

2. 기준 수립 : 회의 시간이 가장 짧은 회의를 우선하여 배정한다.

3. 부분 최적해 : 예약 시간이 1-5, 4-6, 5-10로 주어졌을 경우 가장 짧은 회의는 4-6이다. 하지만 1-5, 5-10 두 회의와 겹쳐 다른 회의는 진행되지 못한다. 즉, 4-6을 선택했을 경우 회의 개수는 1, 1-5, 5-10의 회의를 선택했을 경우 회의 개수는 2개로 회의 시간이 가장 짧은 경우를 우선할 경우 부분 최적해가 성립되지 않는다. 기준 수립부터 다시 시작해야 한다.

 

2. 기준 수립 : 회의 종료 시간이 제일 빠르면서 회의 시작 시간이 가장 느린 순으로 배정한다.

3. 부분 최적해 : 테스트 케이스를 돌려 보면 해당 해가 가장 적절하다는 것을 검증할 수 있다.

 

 

실습

1. 회의실 배정

코드

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

using namespace std;

struct ghldml {
	int start, end;
};

bool cmp(ghldml a, ghldml b) {
	if (a.end < b.end) return true;
	if (a.end > b.end) return false;

	if (a.start < b.start) return true;
	if (a.start > b.start) return false;
	return false;
}

int main() {
	int n;
	cin >> n;
	vector<ghldml> m(n);
	for (int i = 0; i < n; i++) {
		cin >> m[i].start >> m[i].end;
	}
	sort(m.begin(), m.end(), cmp); // 종료시간이 빠르고 시작시간이 느린 순으로 정렬한다.
	int cnt = 1; // 최소 한개의 회의는 열린다.
	int time = m[0].end; // 첫번째 회의의 종료 시간

	for (int i = 1; i < n; i++) {
		if (m[i].start >= time) { // 이전 회의의 종료시간보다는 start가 크거나 같아야 한다.
			// 조건을 만족할 경우
			// 회의 개수 증가
			cnt++;
			// 종료 시간 갱식
			time = m[i].end;
		}
	}
}

 

입력

7
2 4
5 6
2 5
3 5
6 7
1 3
4 7

 

출력

4