[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

경주마 경기

 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안대를 끼고 있습니다. 이를 '차안대' 라고 합니다. 말의 눈은 양 옆에 달려 있어 시야가 '350도'나 됩니다. 자기 자신 빼곤 다 보이기 때문에, 다른 말이 뒤나 앞에서 뛰고 있으면 주의가 산만해지고 피하게 된다고 합니다. 그래서 양 옆의 시야를 차단하는 '차안대'를 착용합니다.

 

[ Contents ]

 

 

1. 그리디 알고리즘

차안대

그리디 알고리즘(Greedy Algorithm): 근시안적인 선택으로 부분적인 최적해를 얻고, 이를 통해 문제의 최적해를 찾는 방식

  '그리디 알고리즘'도 이와 비슷합니다. 최적해를 찾기 위해, '앞'만 보고 달려갑니다. 다시 뒤로 되돌아가지 않으며, 현재 상황에서 최적인 결정을 합니다. 매번 전체적으로 최적인지 고려하는 과정이 없으므로, 빠르고 쉽습니다.

 

 이 때문에 '근시안적'인 알고리즘이라고도 불립니다. 또한 미래를 고려하지 않고 현재 가장 좋은 결정만을 하므로, '탐욕적인 방법' 또는 '욕심쟁이 방법'이라고도 합니다.

 

 

 

2. 그리디 알고리즘 예시와 단점

 일상에서도 우리는 '그리디 알고리즘'을 쉽게 접하고 있습니다. 현재 가장 금리가 좋은 은행에 적금을 맡기고, 현재 가장 먹고 싶은 음식을 먹습니다. 인생도 마찬가지로, 현재 자신의 상황에서 최선의 대학에 지원하고, 최선의 직장에 입사하고, 최선의 차와 집을 삽니다. 현재 가장 좋은 선택이 이어지면, 최적의 선택이 되리라는 믿음이 있기에 가능한 일입니다.

 

 하지만, 우리 인생을 되돌아보면 그 때의 선택이 틀렸음을 간혹 깨닫곤 합니다. 현재 상황에서 가장 좋은 선택이 미래에도 좋다는 보장은 없으며, 그 때문에 '그리디 알고리즘'은 대부분 최적해를 보장하지 못합니다. 하지만 복잡하고 어려운 문제의 해를 비교적 빠르고 쉽게, 좋은 해를 얻을 수 있습니다. 따라서 그리디 알고리즘은 '근사해'(최적에 가까운 해)를 구하는 데에 많이 이용됩니다.

 

 

 

3. 그리디 알고리즘의 최적해 보장조건

탐욕스런 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않음
최적 부분 구조 조건: 문제의 최적해를 부분 문제들의 최적해로부터 쉽게 산출가능

 그리디 알고리즘은 '최적해'를 보장하진 않지만, 위 2가지 조건을 만족하면 최적해를 구할 수 있습니다. 따라서, 그리디 알고리즘으로 문제를 해결할 때에는 위 2가지 조건이 만족하는지 확인해야 합니다.

 

 

 예를 들어, 큰 돈부터 욕심내어 거스름돈을 계산하면 잔돈의 갯수가 최소임을 보장합니다. 잔돈이 700원일 때, 500원부터 고려하면 500원 1개, 100원 2개로 3개입니다. 이는 각 동전의 단위가 배수로 이루어져 있기 때문에 가능합니다.

 반면, 동전 단위가 250 / 100 / 10인 경우에는 최적을 보장하지 못합니다. 잔돈이 300원일 때, 250 + 10*5 보다 100*3개가 최소입니다. 250원이 100원의 배수가 아니므로, 앞의 선택이 이후에 선택에 영향을 주게 됩니다. (탐욕스런 선택조건 불충족)

 

 

 

4. 정리

 그리디 알고리즘은 '당장 지금의 선택 중 최적인 결정'을 이어나가는 문제 해결방식입니다. 한 번 선택하면 번복하지 않으며, 직관적이고 빠르게 최선의 해를 구할 수 있습니다. 현업에서는 어렵고 복잡한 문제의 근사해를 구하는 데에 많이 쓰이며, 코딩테스트에서는 최적해 보장조건을 만족하는 그리디 알고리즘 문제가 출제됩니다.

 최적해 보장조건의 성립여부를 판단하는 게 중요하며, 그리디 알고리즘을 설계하는 건 비교적 쉽게 할 수 있습니다.