최근 수정:
Greedy. 탐욕스럽다는 뜻으로, 현재 가장 좋아보이는 쪽만 선택하는 방식으로 탐색하는 알고리즘.
예를 들면 현재 상태에서 왼쪽이 10, 오른쪽이 1000일 경우 오른쪽이 값이 커서 좋다고 선택하는 방식이다. 물론 오른쪽으로 가는 것이 답이 아닐 수도 있다.
알고리즘 문제를 많이 풀어보지 않은 초보자들이 그리디 방식으로 문제를 풀려는 습성이 있다. 하지만 매우 주의해서 사용해야 한다!
언제 그리디를 사용할까? 지금 이순간 가장 좋은 것을 선택하는 것이 최적일 경우에 사용한다. 따라서 왜 최적이 되는지 증명...까지는 아니더라도 확신을 할 수 있어야 한다.
예를 들어 거스름돈을 최소 개수로 거슬러 주는 경우, 당연히 큰 동전으로 먼저 주는 것이 좋아 보인다. 하지만, 동전들이 배수가 아닐 경우 (1, 5, 6짜리 동전이 있는 경우) 15를 거슬러 줄 때 6을 먼저 사용하면 총 5개 (6+6+1+1+1) 가 필요한데 5 짜리 3개면 가능하다. 이런 문제 때문에 그리디는 직관적으로는 생각하기 쉬울 수 있으나 최적이 아닌 경우가 많다.