그리디 알고리즘은 일반적으로 최적화 문제(Optimization Problem)를 해결하기 위한 방법으로 쓰인다.
최적의 해를 구하기 위해서 반복적인 선택을 하게 되는데, 이때 각 선택마다 현재 상황에서 가장 최적의 선택지를 선택해간다.
이 방법은 '근시안적'인 선택으로 부분 최적해를 찾고, 이들을 모아 문제에 대한 최적해를 얻고자 하는 것이다.
그리디 알고리즘에서는 일단 한번 선택하면, 이를 번복하거나 취소하지 않는다. 따라서 대부분의 그리디 알고리즘은 단순하다.
단, 소수의 문제만이 그리디 알고리즘으로 정확한 해를 구할 수 있다.
부분 최적 해를 선택하는 것이 항상 전체의 최적 해를 구한다는 보장을 할 수 없기 때문이다.
이를 보장하기 위해서는 몇 가지 조건이 필요하다.
- 현재의 선택이 미래의 선택에 영향을 주지 않는다.
- 부분 최적 해가 모이면 전체 최적 해가 된다. 이를, 최적 부분 구조 조건(Optimal Substructure)라고 한다.
즉, 매번의 선택이
어떤 알고리즘이 항상 전체 최적 해를 구한다는 것을 주장하기 위해서는 논리적인 증명이 필요하다.
만약 증명할 수 없다면 알고리즘의 해는 부분 최적 해일 수 있다. 이 경우 휴리스틱 알고리즘(heuristic algorithm) 이라고 부른다.
휴리스틱 알고리즘의 성능은 실험에 의해 조사된다.
위 특징을 가지고 그리디 알고리즘으로 어떻게 문제에 접근해야 할까? 시작은 정렬이다.
문제의 조건와 주어진 데이터의 특징을 잘 고려하여 데이터를 정렬 한 다음, 앞에서부터 최적의 해를 선택해가는 방식으로 접근한다.