그리디(Greedy)란?
지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
Greedy를 푸는 과정
- 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
- 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
- 믿음을 가지고 구현해서 문제를 통과한다.
코딩테스트에서의 추천 전략
Case 1
거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다.
-> 짜서 제출해보고, 틀리면 빠르게 손절 (멘탈이 흔들려도 다음 문제로 Go)
Case 2
100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
-> 일단은 넘어가고 다른 문제를 풀 게 없거나 종료가 20-40분 남은 시점에 코딩 시작
💡 사실 그리디 문제가 아닌데 그리디라고 착각하는 경우가 더 많으니 안되면 넘어가는 전략!
연습 문제
- 11047번: 동전 0 (링크)
- 1931번: 회의실배정 (링크)
- 명제: 현재 시간이 t라고 할 때, 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해이다.
- 귀류법으로 증명
- 현재 시간이 t라고 할 때, 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의(A)가 아닌 다른 회의(B)를 택했을 때 더 많은 회의를 배정할 수 있다고 가정
- 회의 A를 택했을 때 적어도 회의 B를 택했을 때만큼의 회의는 진행할 수 있다는 게 보장
- 가정이 모순
귀류법이란?
어떤 명제가 참임을 증명하려 할 때 그 명제의 결론을 부정함으로써 가정(假定) 또는 공리(公理) 등이 모순됨을 보여 간접적으로 그 결론이 성립한다는 것을 증명하는 방법
- 2217번: 로프 (링크)
- 명제: 각 로프가 버틸 수 있는 최대 중량의 최솟값 * 로프의 개수가 정답이다.