[알고리즘] 탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘(Greedy Algorithm) 이란?

Greedy: (형용사) 탐욕스러운, 욕심 많은

 

"매 선택에서 현재 가장 최적인 답"을 선택해 전체에서 최적의 결과를 도출하는 알고리즘 기법입니다.

순간마다 선택 가능한 경우의 수 중에서, 가장 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행합니다. 최적의 경로만을 찾아 탐색하게 되므로 모든 경로를 탐색할 필요가 없습니다. 이 때문에 속도가 매우 빠른 알고리즘으로 자주 사용될 수 있습니다. 하지만, 그 결과가 최적이라는 보장은 없습니다. 아래의 예시로 설명해 드리겠습니다.

 

위 그래프는 A에서 출발하여 최종 목적지인 E로 가는 경로를 선택하는 예시입니다. A에서 출발하여 다음 선택 가능한 B, C, D 중에 가장 가중치가 낮은 1인 간선을 골라 C로 이동하는 경로를 선택하게 됩니다. 그 다음 차례에서는 선택 가능한 경로가 150의 가중치인 간선밖에 없으므로, 최종 'A->C->E'를 선택하게 되는거죠.

실제로 최적 경로는 'A->B->E'를 선택하여 11의 가중치를 취하여 선택해야 하지만, 그리디 알고리즘 경로는 'A->C->E'를 선택하여 151의 가중치를 취하여 최적값이 아닌 결과를 낳게 됩니다.

이처럼 매 선택의 순간마다 '부분 최적해'는 구했지만, 결과적으로 '전체 문제에서의 최적해'는 구하지 못한 것입니다.

 

 

2. 그리디 알고리즘의 조건

이러한 오류를 방지하기 위해 다음 2가지 조건을 만족해야 합니다.

 

1) 탐욕 선택 속성(Greedy Choice Property)

이전의 선택이 이후에 영향을 주지 않아야 한다.

2) 최적 부분 구조(Optimal Substructure)

부분 문제의 최적결과가 전체에도 그대로 적용되어야 한다.

 

 

어디서 많이 본 조건인데, 이는 DP(Dynamic Programming)의 조건과 비슷해 보입니다. 우선 DP 방법론의 조건은 다음과 같습니다.

 

1) 겹치는 부분 문제(Overlapping Subproblems)

동일한 작은 문제들이 반복하여 전체의 문제와 겹친다.

 

2) 최적 부분 구조(Optimal Substructure)

부분 문제의 최적결과가 전체에도 그대로 적용되어야 한다.

 

여기서 그리디 알고리즘의 조건 2번과 DP 방법론의 조건 2번은 동일합니다. 하지만 조건 1번이 다름을 주의해야 합니다. DP 방법론같은 경우는 문제가 겹쳐지게 되어 다음에 풀 문제가 이전의 작은 문제 결과에 영향을 미칩니다. 피보나치 수열을 예로 들자면, F(5) = F(4) + F(3)과 같은 식에서 F(3), F(4)가 겹치는 문제 풀이이면서 F(3), F(4)의 결과값이 F(5)에 영향을 줍니다.

하지만 그리디 알고리즘에서는 위 그래프에서의 예시를 다시 들어, A에서 출발하여 B or C or D를 선택한 간선의 가중치가 그 다음 E로 향하는 간선을 선택하는데 영향을 주지 않습니다. 즉, 이전에 선택한 가중치가 다음 선택한 가중치에 영향을 주지 않는 형태 입니다.

 

이러한 조건을 잘 고려하여 그리디 알고리즘으로 해결할 수 있는 문제인지 결정지어 방향을 정해야 합니다.