[알고리즘] 그리디 알고리즘 / Greedy Algorithm

그리디 알고리즘은 현재 가장 좋아보이는 선택을 하는 알고리즘이다.

다시 말해, 순간마다 최적의 선택을 진행하여 적합한 해를 도출하며, 그것이 전체의 최적이 될 것이라고 생각한다.

문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되며, 이를 최적 부분 구조라고 한다.

이러한 특성으로 인해, 그리디 알고리즘은 장점과 단점이 뚜렷한 알고리즘이다.

장점은 각 부분에서 최적의 선택을 진행하기 때문에 계산 속도가 빠르다.

단점은 부분에서만 최적을 계산하기 때문에 전체적으로 봤을 떄 최적이 아닐 가능성이 있어 도출된 해가 최적임을 보장하지 않는다.

 

 

그리디 알고리즘은 Greedy-Choice Property(탐욕적 선택 속성)과 Optimal Substructure(최적 부분 구조)를 만족하는 문제를 해결하는데 사용할 수 있다.

탐욕적 선택 속성은 Local Optimum(한 순간에서의 최적)을 선택해서 풀이할 때 최종적으로 Global Optimum(전체 최적)에 도달할 수 있는 가능성이며, 

최적 부분 구조는 최적해를 구할 때 하위 문제에 대한 최적해를 찾은 후 결합하면 전체 문제의 최적해가 되는 경우를 말한다.

따라서, 순간의 선택이 다음 선택과 무관해야 하며, 그 순간의 최적해가 문제 전체의 최적해가 되어야 한다.

예를 들어 knapsack problem같은 경우 fractional과 0-1방식이 있는데, (물건을 나눠서 가져가는 방식 / 통째로 가져가는 방식) fractional 방식에서 무게 당 가치만 생각해서 가방에 담다 보면 문제의 최적해를 구할 수 없는 경우가 발생한다.

그렇기 때문에 0-1 knapsack problem은 동적 계획법을 사용하여 문제를 해결한다.

이렇듯, 그리디 알고리즘은 장점과 단점이 너무나 뚜렷하기 때문에 문제를 잘 파악해 탐욕적 선택 속성과 최적 부분 구조를 만족하는지 알아낸 후 사용하는 것이 좋다.