Greedy

• 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
• 관찰을 통해 탐색 범위를 줄이는 알고리즘
• 그리디 정의에 잘 맞는 알고리즘 ⇒ merge sort
  • 관찰을 통해 O(N+M)에 풀 수 있음

Greedy의 이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법 고안
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명
   1. 증명을 하게 되면 그리디 풀이의 논리적인 반례를 잡아 낼 때도 도움이 됨
   2. 그리디 풀이가 올바른지 머리로 생각할 수 있도록 도움을 줌
3. 구현해서 문제를 통과

코테에서의 Greedy 추천 전략

• 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다
  • 짜서 제출해보고 틀리면 빠르게 손절
• 100%확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
  • 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에 코딩 시작
• 코딩 테스트에 잘 나오는 유형은 아님

<aside> 🔥 Greedy 연습 문제

<aside> 🔥 BOJ 11047 동전 0)

D[i] = 가치의 합을 i로 만들 때 필요한 동전 개수의 최솟값

• 잘못된 풀이
  • D[i] = min(D[i-A_1], D[i - A_2], … , D[i - A_N]) + 1 (코드 ⇒ 런타임 에러)

보조 정리 1

동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다.

귀류법)

10/100원 동전을 5개 이상 사용 → 50/500원 동전 대체

50원 동전을 2개 이상 사용 → 100원 동전으로 대체

명제)

동전을 최소로 소모하면서 물건 값을 지불하려면 500원 동전을 최대한 많이 써야 함

증명)

10, 50, 100 동전으로는 물건값을 최대 490원 감당 가능, 500원을 다 사용하지 않을 경우 10, 50, 100 동전으로 500원 이상 감당해야 함

반례)

1원, 9원, 10원 동전이 있을 경우, 18원 동전을 나눌 때에는 9원 2개가 가장 효율적이지만 10원부터 사용하기에 10원 1개, 1원 8개 총 9개를 사용하는 비효율적인 값이 나올 수 있다.

주의할 점)

풀이의 방향을 한정 짓지 말아야 한다.

#include <bits/stdc++.h>
using namespace std;
/* n = 동전의 개수, k = 총 가치의 합 */
int n, k;
int a[15];

int main(void){
	int ans = 0;
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = n - 1; i >= 0; i--){
		/* 가치가 가장 큰 동전부터 순차적으로 나누어짐 */
		/* 동전 개수 카운팅 */
		ans += k /a[i];
		/* 남은 값 (그 다음 동전으로 위를 반복) */
		k %= a[i];
	}
	cout << ans;
}

</aside>

</aside>

<aside> 🔥 Greedy 연습 문제

<aside> 🔥 BOJ 1931 회의실 배정)

1. O(2^N)
   • 모든 가능한 배정 방법 확인

• O(N^2)
  • 회의를 끝나는 시간이 빠른 순으로, 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬
  • D[i] = i번째 회의를 마지막으로 진행했을 때 최대 회의의 수
  • D[i] = max(D[j]) + 1 (j번째 회의의 끝나는 시간이 i번째 회의의 시작 시간 이하인 모든 j)

명제)

현재 시간이 t 라고 할 때 시작 시간이 t이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해이다.

증명)

회의 A 대신 회의 B를 택했을 때 더 많은 회의를 배정할 수 있다고 가정 → 회의 B 대신 A를 사용해도 아무런 모순이 발생하지 않음

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> s[100005];

int main(){
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> s[i].second >> s[i].first;
	sort(s, s+n);
	int ans = 0;
	int t = 0;
	for(int i = 0; i < n; i++){
		if(t > s[i].second) continue;
		ans++;
		t = s[i].first;
	}
	cout << ans;
}

끝나는 시간이 빠른 것이 앞에 있어야 함 ⇒ 동일하면 시작하는 시간이 빠른 것이 앞에 있어야 함

</aside>

</aside>