그리디 알고리즘

그리디 알고리즘은 현재 상황에서 가장 좋은 것만 고르는 방법을 말한다.

(그런 점에서 다익스트라 알고리즘도 그리디 알고리즘의 종류라고 할 수 있다.)

즉, 매 순간 최선의 옵션을 선택한다고 할 수 있다.

최단 경로 알고리즘의 유형들이나 정렬 알고리즘과는 달리 사전에 풀이 방법을 외우고 있지 않아도 풀 수 있는 문제 유형인 경우가 많다.

 

그리디 알고리즘임을 파악할 수 있는 경우는, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 제시해준다.

 

대부분의 문제는 그리디 알고리즘으로 접근했을 때 '최적의 해' 를 구할 수 없다는 단점이 있다.

대표적인 동전 거슬러주기 문제 경우에도 동전의 단위가 가장 각 동전들의 약수인 경우에만 그리디 알고리즘으로 해결이 가능하다. (서로 배수 관계가 아닌 경우는 DP 로 해결할 수 있는데, 추후 포스팅에서 다룰 예정이다)

 

코테에 나온 문제가 어떤 알고리즘 접근법을 사용하면 좋은지 파악하기 어려운 경우는

   1) 그리디 알고리즘

   2) DP (Dynamic programming)

   3) 그래프 알고리즘

이 아닌지 검토해 보는 과정이 필요하다.

 

참고 문헌

이것이 코딩테스트다, 나동빈 저