[Greedy] 그리디 알고리즘 개요

그리디 알고리즘

 

정의: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 모든 문제에 적용 불가. 하지만, 탐욕적으로 문제에 접근해 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적인 알고리즘이다.

 

즉, 나중의 선택에서 효율적인 반례가 나오면 이 알고리즘을 사용하지 않는 것이 좋다.

 

문제에 적합한 알고리즘 파악 Flow: 어떤 코딩테스트 문제를 만났을 때, 바로 문제 유형 파악이 힘들다면 그리디 알고리즘을 의심 -> 해결이 어렵다면, 다이나믹 프로그래밍 및 그래프 알고리즘 등으로 문제 해결 할 수 있는지 고민해본다.

 

문제의 특성:  그리디 알고리즘의 문제 출제의 폭이 넓기 때문에, 다익스트라 알고리즘(다익스트라 알고리즘도 그리디 알고리즘에 속한다.) 같은 특이 케이스를 제외하고 암기로는 모든 문제를 대처하기는 힘들다. 정렬 알고리즘과 자주 짝을 이루며 문제가 출제되기도 한다.