그리디(Greedy)란?
지금 가장 최적인 답을 근시안적으로 택하는 알고리즘

Greedy를 푸는 과정

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
3. 믿음을 가지고 구현해서 문제를 통과한다.

코딩테스트에서의 추천 전략

Case 1

거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다.
-> 짜서 제출해보고, 틀리면 빠르게 손절 (멘탈이 흔들려도 다음 문제로 Go)

Case 2

100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
-> 일단은 넘어가고 다른 문제를 풀 게 없거나 종료가 20-40분 남은 시점에 코딩 시작

💡 사실 그리디 문제가 아닌데 그리디라고 착각하는 경우가 더 많으니 안되면 넘어가는 전략!

연습 문제

1. 11047번: 동전 0 (링크)

---

2. 1931번: 회의실배정 (링크)

• 명제: 현재 시간이 t라고 할 때, 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해이다.
• 귀류법으로 증명
  - 현재 시간이 t라고 할 때, 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의(A)가 아닌 다른 회의(B)를 택했을 때 더 많은 회의를 배정할 수 있다고 가정
  - 회의 A를 택했을 때 적어도 회의 B를 택했을 때만큼의 회의는 진행할 수 있다는 게 보장
  - 가정이 모순

귀류법이란?
어떤 명제가 참임을 증명하려 할 때 그 명제의 결론을 부정함으로써 가정(假定) 또는 공리(公理) 등이 모순됨을 보여 간접적으로 그 결론이 성립한다는 것을 증명하는 방법

---

3. 2217번: 로프 (링크)

• 명제: 각 로프가 버틸 수 있는 최대 중량의 최솟값 * 로프의 개수가 정답이다.