[알고리즘] 탐욕(그리디) 알고리즘

그리디 알고리즘이란?

탐욕적 알고리즘이라고도 하며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

 

A에서 C까지 가는 최단 경로는?

 

A에서 B로 갈 때 가장 적은 비용인 20을 고른다.

B에서 C로 갈 때 가장 적은 비용인 8을 고른다.

A에서 C로 가는 최단 경로는 20+8=28인 것을 알 수 있다!

이 문제는 선택의 순간마다 가장 적은 비용이 드는 길을 찾아가는 방법으로 풀 수 있었다.

 

 

아래의 문제도 위와 같이 그때그때 가장 최적의 값을 고르는 방법으로 풀어야 할까?

 

총 합이 최대의 값을 얻는 방법은?

위의 방법처럼 그때그때 최적의 값을 골라보자.

start에서 시작하여 최대의 값을 얻어야 하니 15로 가보자.

15에서 또 다시 최대의 값을 얻기 위해서는 20을 골라야 한다.

start-15-20 경로의 총합은 35이다.

이번에는 start에서 4방향으로 가보자.

4에서 최대의 값을 얻기 위해서는 50으로 가야한다.

start-4-50 경로의 총합은 54이다.

 

이처럼 그때그때 최적의 값을 선택하는 것이 항상 답이 되지는 않는다.

 

 

그리디 알고리즘을 만족하기 위한 조건

1. 탐욕적 속성

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

즉, 탐욕적으로 한 선택은 항상 최적해로 가는 길이다.

2. 최적 부분 구조

문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해라는 것