[알고리즘 공부] 그리디 알고리즘 Greedy Algorithm

그리디 알고리즘이란?

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자." 라는 모토를 가지는 알고리즘 설계 기법이다.

정치적으로 보면 당면한 경제 문제를 가장 빠르게 해결해 줄 것이라고 여기는 대통령을 찍거나 당면한 지역 인프라 과제를 가장 빠르게 해결해 줄 것이라고 여기는 시장·군수·도지사 또는 국회의원을 찍는 의사결정 행위로 볼 수 있다. 또한 유명한 마시멜로 실험에 비유할 수 있다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 계속해서 먹는것이다. 

하지만, 이 그리디 알고리즘을 사용하여 도출된 결과값은 항상 가장 최적의 결과를 보장해주지는 않는다. 위의 예시와 같이 지금 당면한 문제를 가장 빨리 해결할 수 있는 후보를 선택한다고 해서 그것이 가장 최적의 선택은 아닐것이며, 눈앞의 마시멜로를 계속 먹는다면, 조금 더 기다렸다가 마시멜로 2개를 먹는 선택지는 전혀 고려할 수 없다.

따라서, 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 아래에서 이 두가지 특성에 대해 알아보자.

 

탐욕 선택 속성 Greedy Choice Property

이전의 선택이 이후에 영향을 주지 않아야 한다는 조건이다. 현재의 선택은 이전까지의 선택에 따라 달라지지만, 앞으로의 선택에 의해서 현재의 선택이 달라지지 않는다는 것이다. 즉, 일단 현재 순간의 최적해를 한번 선택하면, 이를 다시는 번복하지 않는다. (백-트래킹을 하지 않는다.) 이는 동적 계획법 (DP : Dynamic Programming) 과 가장 큰 차이점으로, 모든 단계를 끝마치고 이전으로 돌아가 재고하는 과정이 없다는 의미이다.

 

최적 부분 구조 Optimal Substructure

 

위 그림을 보고 최적 부분 구조에 대해 더 이해해보자. 서울에서 대구를 거쳐 부산까지 가는 최단 경로를 찾는다고 가정해보자. 총 경로의 경우의 수는 3x3=9이다. 그중 가장 최단경로로 가는 경우는 서울-대구 경로에서 200km를 선택하고, 대구-부산 경로에서 80km를 선택하는 경우인 총 280km짜리 경로이다. 따라서, 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다. 이러한 구조를 최적 부분 구조라고 한다.

 

이렇게 두 조건이 전부 만족하는 상황이어야 그리디 알고리즘을 성공적으로 적용할 수 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며, 매 순간의 최적해가 전체 문제에 대한 최적해여야 한다는 의미이다.