[필수 알고리즘] 그리디 알고리즘(Greedy Algorithm) 이해

그리디 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란,

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.

 

그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

 

루트 노드부터 시작하여 거쳐 가는 노드 값의 최대로 구한다면,

 

 

값은 5+7+9 = 21로 다음과 같지만

거쳐가는 노드의 경우에서 가장 큰 값(최적의 값만) 구한다면,

값은 5+10+4 = 19 가 된다.

 

이처럼, 그리디 알고리즘은 최적의 값을 도출해내지 못하지만 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.

 

그리디 알고리즘 기법 활용

1. 탐욕 선택 속성(greedy choice property)

앞의 선택이 이후의 선택에 영향을 주지 않는다.

 

2. 최적 부분 구조(optimal substructure) 

문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미

 

 

최적 부분 구조 

 

 

서울에서 경기도를 거쳐 부산을 가는 최단 경로를 찾는다.

그림에서 보듯이 3가지 경우들이 있으며 문제를 풀어보면

1. 서울에서 경기도로 가는 최단경로

2. 경기도에서 부산으로 가는 최단경로

각각의 부분문제 최단 경로의 합으로 구해진다.

 

따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법로 구성되고

답은 (서울 -> 경기도) 30km , (경기도 -> 부산) 200km 30+200으로 서울에서 경기도를 거쳐 부산의 최단경로는 230km이다.