알고리즘 개념[실전] - 그리디 알고리즘

참고 포스팅

• https://blog.encrypted.gg/975

그리디 알고리즘이란?

• 매번 선택에서 지금 가장 최적의 답을 근시안적으로 택하는 알고리즘입니다.
• 그리디 알고리즘은 항상 최적해를 만족하는 것이 아닙니다.
  • 경로를 선택할 때를 예로들면, 중간에 경유지가 있고 목적지가 있는 경우 경유지 까지 가장 짧은 거리의 경로를 선택했지만, 다른 경로의 경유지부터 목적지까지의 경로가 훨씬 짧아 전체 거리는 가장 짧은 최적해를 구할 수 없게 됩니다.
  • 따라서, 그리디 알고리즘은 항상 최적해를 구하는 것이 아닌 최적해에 근사하는 방법일 뿐입니다.
• 비슷한 말로, 관찰을 통해 탐색 범위를 줄이는 알고리즘을 말합니다.
• 해당 유형은 많은 문제 유형을 풀어봐야 하는 것으로, 비슷한 유형의 문제가 나오면 풀 수 있지만, 아닌 경우 못 풀 확률이 높습니다.

이상적인 풀이 흐름

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

코테에서의 추천 전략

• 비슷한 유형의 문제를 풀어봤고 해당 문제의 구현이 간단한 경우, 나의 그리디 풀이를 100% 확신한다.
  - 생각대로 구현 및 제출해보고 틀릴 경우 빠르게 손절
  
• 100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
  - 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에서 코딩 시작.