그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

그리디 알고리즘

그리디 알고리즘(Greedy Algorithm )이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.

그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려우면 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다.

그리디 알고리즘은 탐욕 선택 속성Greedy Choice Property를 가지고 있는 최적 부분 구조Optimal Substructure인 문제들이다. 여기서 탐욕 선택 속성 이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다.

즉, 그리디 알고리즘은 선택을 다시 고려하지 않는다.

또한, 최적 부분 구조 란 문제의 최적 해결 방법이 부분문제에 대한 최적 해결방법으로 구성되는 경우를 말한다.

이렇게, 두가지 조건을 만족하면 최적해를 찾을 수 있다. 그러나, 그렇지 않다해도 그리디 알고리즘은 정답을 근사하게(approximately) 찾는 용도로 활용할 수 있으며, 대부분의 경우 계산 속도가 빠르므로 실용적이다.

그리디 알고리즘이 작동하는 사례는 다음과 같다.

• 다익스트라 알고리즘: 대표적인 그리디 알고리즘의 예로서 최적해를 찾을 수 있다.
• 허프만 코딩 알고리즘: 허프만 트리를 빌드할 때 그리디 알고리즘을 사용하며, 마찬가지로, 최적해가 보장된다.
• ID3 알고리즘: 의사결정 트리 알고리즘으로 유명한 이 알고리즘이 그리디 알고리즘이다. 항상 그때 그때 최선의 답을 찾아 트리를 빌드해 나간다. 이경우는 최적에 가까운 답을 찾을 수 있지만, 반드시 최적해를 찾는 것은 아니다. 앞에서 말한 근사한 답을 찾는 용도이다.

그리디 VS 다이나믹 프로그래밍

그리디 알고리즘이 최적 부분 구조 문제를 푼다는 점에서 흔히 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근방식 또한 다르다.

다이나믹 프로그래밍이 하위 문제에 대해 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다면,

이에 반해 그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태로, 서로 반대 방향으로 접근하는 구조를 띤다.