lks의 코딩일기

1. 그리디 알고리즘이란?

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

예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.[1] 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 아래의 그림에서 1~6까지의 최소 경로를 찾아볼 때 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

그리디 알고리즘을 한마디로 설명한다면 그 유명한 마시멜로 실험에 비유할 수 있겠다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

2. 어떤 경우에 잘 동작하는가

그리디 알고리즘은

1.탐욕스러운 선택 조건 (Greedy choice property)
앞의 선택이 이후의 선택에 영향을 주지 않는 조건.

2.최적 부분 구조 조건(Optimal Substructure)
문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다는 조건.

특성을 가지는 문제들을 해결하는데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다. 

3.그리디 알고리즘 적용가능한  예

그리디 알고리즘을 적용가능한  예시에는

Prim Algorithm, Kruskal Algorithm이 있다.

그 외도, 가중치가 있는 방향 그래프에서 최단거리를 구해주는 Dijkstra Algorithm, 거스름돈 나누기 등이 있다.