그리디

<설명>

1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다.

(그리디로 풀리면 보통 dp로도 풀린다)

2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다.

 

ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다.

 

 

<정당성 증명>

탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성

 

최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지

->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재

 

알고리즘이 위 두 속성을 만족하는지 검증해야 한다.

 

 

 

 

---

 

1. 활동 선택 문제 (activity - selection problem)

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

스케줄 (시작시간, 끝시간)에 대한 정보들이 입력될때, 최대한 많은 스케줄을 이행하기 위해서는 어떻게 해야할까? -> 끝나는 시간 기준으로 정렬 후 순서대로 처리하면 된다.

 

https://helloworld2016.tistory.com/24?category=655741

위 블로그의 첫번째 예시를 참고하자.

 

<정당성 증명>

(탐욕적 선택 속성)

탐욕적 선택 속성이 성립 ~ '가장 종료시간이 빠른 스케줄 (sm)을 포함하는 최적해가 반드시 존재한다.' 성립

 

귀류법 사용:

최적해 중에 sm을 포함하지 않는 답(서로 겹치지 않는 스케줄 목록)이 있다고 가정.

 

이 목록에서 첫번째로 개최되는 회의를 지우고 sm을 대신 추가해서 새로 답을 만들어도 최적해 중 하나가 된다.

 

따라서 항상 sm을 포함하는 최적해가 존재한다.

 

(최적 부분 구조)

첫 번쨰 회의를 잘 선택했다면 나머지 유효한 회의 중 최대한 많은 회의를 선택해야 한다.

 

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
int n;
pair<int, int> s[100005]; 

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> s[i].second >> s[i].first;
	
	sort(s, s + n); 
	int cnt = 0;
	int t = 0; // 현재 시간
	for (int i = 0; i < n; i++) {
		if (t > s[i].second) continue; 
		cnt++;
		t = s[i].first; 
	}
	cout << cnt;
}

 

 

---

2. 강의실 배정 *

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

시작시간, 종료시간으로 강의들의 정보가 입력된다. 이 떄, 최소한의 강의실을 사용해서 모든 수업을 가능케하려면 몇 개의 강의실을 사용해야 할까? -> 시작시점 기준으로 정렬한 후 처리한다.

 

모든 강의에 대해 [시작,끝) 구간을 나타내는 선분을 만들어보자.
앞에서부터 라인 스위핑을 할 때, 최대로 교차되는 선분 개수가 답이다.

 

pq를 사용해서 쉽게 해결할 수 있다.

 

https://suuntree.tistory.com/221

 

 

---

3. 작업과 데드라인

작업 n개의 소요시간과 데드라인을 주어질 때 각각의 작업을 완료하면 점수 di-xi점을 얻는다. 이때 어떤 순서로 작업을 수행하는 것이 좋을까? -> 소요시간 순서대로 작업하면 된다. 그러면 데드라인이 어떻게 부여됐는지는 전혀 상관없다.

 

위와 같이 소요시간이 a인 작업 X와 소요시간이 b인 작업 Y를 생각해보자. (a>b)

 

이 둘의 작업 순서를 바꾸게 된다면 작업 Y의 점수에 대해서 a만큼의 이득을 보는 것이고, 작업 X의 점수에 대해선 b만 큼 손해를 보게 된다. 그럼 전체 점수는 a-b만큼 변하게 되는데 a>b이므로 항상 이득이다.

 

/*
입력
4
4 2
3 10
2 8
4 15
출력
6
*/
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
const int MAX = 1e5 + 5;
typedef pair<int, int> pii;

int n;
pii p[MAX]; //소요시간, 데드라인

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i].first >> p[i].second;

	sort(p, p + n);

	int sum = 0, ctime = 0;
	for (int i = 0; i < n; i++) {
		int t = p[i].first, d = p[i].second;

		ctime += t;
		sum += d - ctime;
	}

	cout << sum << '\n';
}

 

---

<두명이 n개의 책을 모두 읽기>

https://cses.fi/problemset/task/1631

최대 2e5개의 책을 두명이서 읽기로 한다. 각 책을 읽는 시간이 주어질 때 두명이 모든 책을 읽는데 걸리는 최소시간ㅇ르 구해라. (동시에 같은책을 읽을 수 없음)

 

->최대값이 나머지의 합보다 크다면 2*m, otherwise, sum

 

const int MAX = 2e5 + 2;

int main() {
	FAST;
	ll n, x, m = 0, s = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		m = max(m, x);
		s += x;
	}
	cout << (m > (s - m) ? 2 * m : s) << '\n';
}