그리디 알고리즘( Greedy Algorithm )이란?

• 각 단계마다 지역적 최적의 해가 궁극적으로 전역 최적의 해가 되는 것을 말합니다. 지금의 state 혹은 idx에서 최선이라고 생각하는 해가 결국은 이 문제의 답이 되는 것입니다.

그리기 알고리즘 두 가지 조건

• 최적 부분 구조를 가지고 있어야 합니다. 지금 이 state에서 최선을 다해 선택하는 해가 결국에는 전역적인 최적해로 이어져야 합니다.

• 탐욕적 속성이 증명이 되어야 합니다. 보통 귀류법으로 증명을 합니다.

증명의 한계

• 그리디 알고리즘으로 풀기 위한 조건을 확인하기 위해서 코딩 테스트에서 증명까지 하는 것은 다소 무리가 있습니다. 그렇기 때문에 문제를 파악했을 때 너무 큰 공간, 너무 큰 시간 복잡도를 요구하는 문제라면은 "무식하게 풀기 -> DP -> 그리디 알고리즘" 순서로 문제에 접근해야 합니다. DP도 공간 복잡도의 한계 때문에 적합하지 않는 경우가 있는데 그럴 경우 그리디 알고리즘을 이용해 접근할 수 있습니다.

자료 참조 : https://blog.naver.com/jhc9639/222319124359