11/2 TIL | 그리디 알고리즘(Greedy Algorithm)

오늘 코딩 도장 문제 풀이를 하다가 문제에 해당하는 알고리즘이 '그리디 알고리즘(Greedy Algorithm)'에 해당된다는 것을 알게 되었고, 그렇다면 오늘의 TIL은 그리디 알고리즘을 정리해봐야겠다는 생각이 들었다!

---

그리디 알고리즘은 한국어로는 탐욕(내지는 욕심쟁이) 알고리즘이라고 하는데 이는 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과(= 최적해)를 도출하자"는 모토를 가지고 있기 때문에 이렇게 탐욕이라는 의미를 붙인 것이라 생각된다. (한순간도 최고의 선택을 놓칠 수 없는 당신은 욕심쟁이 우후훗!!!🤗)

우선 그리디 알고리즘을 알아보기 전에 동적 계획법(Dynamic Programming)부터 알아야 한다. 동적 계획법 또한 최적화 이론 중의 한 기술로, 특정 범위까지의 합을 구하기 위해서 그것과 다른 범위까지의 값을 이용하는 알고리즘이다. 즉, 전체 문제를 여러 개의 하위 문제로 나눠 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제의 해결법을 도출하는 방식의 알고리즘이다. 대표적인 예시로는 피보나치수열 구하기 등이 있다.

다만 동적 계획법의 경우, 해답을 구하기 위해 지나치게 많은 일을 한다는 크나큰 단점이 있었기에 이 점을 착안하여 고안된 알고리즘이 바로 그리디 알고리즘이다. 그리디 알고리즘은 앞서 말했다시피 미래까지 생각하지 않고 현재의 가장 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘을 설명하기 위해서 마시멜로 실험을 예로 들 수 있다. 

💡마시멜로 실험이란?
스탠퍼드에서 진행한 실험으로 어린아이에게 마시멜로 1개를 주고, 15분 동안 먹지 않고 참으면 2개를 주기로 하고 행동을 관찰했을 때, 먹지 않고 참은 아이들이 자라서 그렇지 않았던 아이들보다 학업 성취도 측면에서 더 우월한 결과를 보인다는 연구 결과를 가진 실험이다.

이때 그리디 알고리즘을 사용한다면, "지금 당장 눈앞에 있는 마시멜로를 먹는 것"이 그리디 알고리즘의 해답이기 때문에 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다. 그리디 알고리즘은 부분의 최적해의 집합이 곧 전체 문제의 해답이 될 때 사용해야 한다. 그러니까 위의 마시멜로우 실험은 그리디 알고리즘으로 해결할 수 없는 문제였다.

그렇다면 어떤 경우에 제대로 동작할 수 있을지 알아보자. 그리디 알고리즘은 탐욕 선택 속성이나 최적 부분 구조의 특성을 가진 문제를 해결할 때 빛을 발한다. 즉, 한 번의 선택이 다음 선택과 유기적으로 연결되는 것이 아니라 매번 무관해야 하고, 매 순간의 최적해가 문제에 대한 최적해여야 한다는 것이다.

그리디 알고리즘의 예

예를 들어 서울에서 대구를 경유하여 부산으로 여행하는 경로 중 최적의 경로를 찾고 싶은 경우를 생각해보자. 그러면 가능한 모든 경로를 경우의 수로 살펴봤을 때 그중 가장 짧은 경로를 선택하는 것이 하나의 전략이 될 수 있다. 이때 그리디 알고리즘을 사용하면 "지금 내가 있는 도시에서 갈 수 있는 도로 중 가장 짧은 도로를 선택한다"는 최적해를 도출할 수 있기 때문에 이 경우에 빛을 발할 수 있는 알고리즘이다. 이와 같이 문제의 최적의 해결 방법이 바로 부분 문제에 대한 최적의 해결 방법으로 구성되는 구조를 최적 부분 구조라고 부른다.

앞서 마시멜로 실험에서도 설명했듯이 그리디 알고리즘은 100% 최적해를 보장하지는 않는다. 다만, 어느 정도 적합한 수준의 해답을 알려주기 때문에 최적이 아닌 "적당히 괜찮은 방법" 혹은 "되는지"를 확인하고 싶은 경우에도 사용할 수 있다. 이경우에는 최적해가 아닌 근사해라고 부른다. 

---

 

[🍀 그리디 알고리즘 최종 정리]

1. 그리디 알고리즘이란 현재 상황에서 가장 최선의 선택을 하는 알고리즘이다.
2. 항상 최적해를 구할 수 있는 경우, 수행 시간이 동적 계획법보다 빠르다.
3. 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용하면 좋다.
4. 항상 최적해를 보장하지 않는다.
5. 제약 사항 때문에 최적해를 찾기 어려운 경우 근사해를 찾을 때 사용할 수 있다.