그리디(Greedy)
그리디 알고리즘이란 최적화 문제를 해결하기 위한 알고리즘 중 하나로, 미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘이다.
즉, 현재 선택이 나중에 어떤 결과를 낳을지는 고려하지 않고, 현재 내릴 수 있는 최선에만 집중한다.
따라서 그리디 알고리즘은 현재 선택이 지역적으로는 최적이지만, 전체적으로는 최적해를 보장하지 않는다. 즉, 현재의 최적해가 항상 전체의 최적해와 같다고 할 수 없다. 이런 점에서 그리디 알고리즘을 근사 알고리즘이라고도 한다.
특징
따라서 그리디 알고리즘은 각 단계에서 최선의 선택을 하면서 문제를 해결하고자 한다. 즉, 그리디 알고리즘은 최적해가 보장되는 상황에서만 사용해야 한다. 그렇다면 최적해를 보장하려면 어떻게 해야 할까?
최적 부분 구조 (Optimal Substructure)
첫 번째로 문제의 최적해가 부분 문제에 대한 최적해를 포함해야 한다. 즉, 부분의 최적해가 모이면 전체의 최적해가 되어야 한다는 의미이다. 하나의 큰 문제를 작은 문제로 나누고, 작은 문제에 대한 최적의 해가 더 해진 것이 곧 전체 문제의 최적해가 되도록 한다.
탐욕적 선택 속성 (Greedy-choice property)
두 번째로 각 단계에서 최적해를 찾기 위해 지금 당장 최적인 선택을 한다. 즉, 현재 선택이 미래의 선택에 영향을 주지 않아야 한다는 의미이다.
따라서 그리디 알고리즘의 핵심은 정렬이다. 앞선 두 가지 조건을 만족하도록 정렬해야만, 최적해를 보장한다는 전제하에 그리디 알고리즘을 사용할 수 있기 때문이다.
그리디 알고리즘은 동적 프로그래밍(DP) 사용 시 지나치게 많은 경우의 수를 고려한다는 것에서 착안하여 고안된 알고리즘이다. 그러나 동적 프로그래밍을 대체하는 것은 아니고 서로 보완하는 개념이다.
그리디 알고리즘은 근사치로도 만족할 수 있을 때 성능을 개선하기 위한 목적을 가진다. 그래서 효율적인 경우가 많다. 그러나 반드시 최적해를 보장하지는 않기 때문에 최적해를 찾아야 하는 경우 문제의 특성을 잘 파악하고 적용해야 한다.
