[TIL] 250628 - 그리디 (Greedy)

바킹독의 실전 알고리즘 강좌를 보고 파이썬 버전으로 정리했습니다.

 

정의

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

 

이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다
   • 실제 코테에서 수학적으로 증명할 시간따위 없으니 대충 주어진 예제에서 잘 돌아가면 그냥 내 풀이는 완벽하다는 믿음을 가지고 가는 메타
3. 구현에서 문제를 통과한다

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

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