그리디(Greedy) 알고리즘

그리디는 "탐욕"이라고 부르는데 있는 그대로 해석하자면 먼저 눈 앞에 있는 것 중에 최선의 선택을 하는 알고리즘이라고 생각하면 될듯하다.

 

이 알고리즘은 매순간 최선의 선택을 하게 되지만 그렇다고 결과값이 최선의 값이 나오지 않는다.

예를들어

예시 트리

위와 같은 트리 구조가 있을 때

위 순서대로 내려갔을 때, 내려간 수의 합을 구하시요 

라고 한다면

그리디 알고리즘을 사용한다면 20+30+50 = 100 의 값이 나오지만,

사실 더 큰수를 찾는 방법은 20+10+150 = 180이 우리가 찾던 정답이 나올 수 있다는 것이다.따라서 항상 매 분기마다 최선의 선택을 하지만, 그 결과값이 최선은 아닐 수 있다는 사실을 명심해야한다.