그리디

그리디

Greedy
= 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
= 관찰을 통해 탐색 범위를 줄이는 알고리즘

이상적인 풀이순서

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.
3. 구현해서 문제를 통과한다.

위와같이 풀면 좋겠지만, 이건 너무나도 이상적인 풀이이다.

간혹 아래와 같은 그리디 유형 풀이 접근시도가 나타날 수 있다.

절망적인 풀이흐름

1. 관찰을 통해 탐색범위를 줄이는 잘못된 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
3. 믿을 가지고 구현했는데 계속 틀린다.

코딩테스트에서 그리디 유형 풀이전략

CASE1) 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신하는 경우

• 짜서 제출해보고 틀리면 빠르게 손절

---

CASE2) 100% 확신은 없지만 맞는것 같은 그리디 풀이를 찾은 경우

• 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에 코딩 시작

• 그리디가 그렇게 코테에 자주나오는 유형도 아니고,
  오히려 그리디로 풀수없는 문제인데 그리디로 착각해서 잘못된 길로 빠져드는 일을 겪기가 쉽다.

따라서 그리디로 풀 수 있는 것같은 문제더라도 바로 풀이를 시작하기보단,
정말 100% 확신할 수 없다면 바로 풀이를 시작하지말고 다른 문제를 푸는것이 낫다.