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

그리디 알고리즘은 원하는 답을 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어가는 방식이다.

이는 완전 탐색이나 동적 계획법과 유사하지만 각 단계마다 지금 당장 가장 좋은 방법만 선택한다.

즉 이 방식은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

 

이렇게 문제를 해결하는 경우 최적해를 찾지못하는 경우가 많아진다.

그럼에도 그리디 알고리즘이 사용되는 경우는 아래 두 가지가 있다.

1) 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있느 문제를 만난 경우, 이는 동적 계획법보다 수행시간이 훨씬 빠르다.

2) 시간이나 공간적 제약으로 인해 다른 방식으로 최적해를 찾기 힘든 경우 대신 적당한 근사해를 찾는 것으로 타협할 수 있다. 이때 그리디 알고리즘은 최적은 아니나 임의의 답 보다는 좋은 답을 구하는 용도로 유용하다.

 

 

알고리즘의 정당성 증명

1) 탐욕적 선택 속성

동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다.

2)최적 부분 구조

항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 보여야 한다.

 

 

출처: 알고리즘 문제해결 전략(구종만)