그리디 알고리즘

그리디 알고리즘이란?

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만 쫓아 최종적인 해답에 도달하는 법

순간마다 하는 선택은 지역적으로 최적이지만, 최종적인 해답이 최적이라는 보장이 없다.

그래서 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

 

그리디 알고리즘 문제 해결 절차

1.     현재 상태에서 최적의 해답을 선택한다.

2.     선택된 해가 문제의 조건을 만족하는지 검사한다.

3.     문제가 해결되었는지 검사하고, 해결되지 않았다면 1번 과정으로 돌아가 위 과정 반복

 

그리디 알고리즘 조건 2가지

탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조 : 문제에 대한 해결 방법은 부분 문제에 대한 최적 문제 해결 방법

 

탐욕 알고리즘이 항상 최적의 결과를 도출하는 것은 아니다.

하지만 최적의 근사치를 빠르게 도출할 수 있다는 장점이 있다.

탐욕 알고리즘을 적용해도 언제나 최적의 해를 구할 수 있는 문제(매트로이드)가 있다. 이 문제에서 실용적으로 사용할 수 있다.