탐욕 알고리즘 - 개요

탐욕 알고리즘이란?

입력 데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심 내어 최솟값 또는 최댓값을 가진 데이터를 선택하는 알고리즘

• 한 번 선택 시 선택한 데이터를 버리고 다른 것을 취하지 않는다.
• 이러한 특성 때문에 탐욕 알고리즘들은 매우 단순, 제한적인 문제들만 해결 가능하다
• Prim, Kruskal 알고리즘이 탐욕 알고리즘에 해당한다

순간의 선택이 최선인 이유

그리디 알고리즘이 사용되기 위해 필요한 조건 2가지를 만족했을 때 사용하면 그리디 알고리즘은 순간의 선택에서 최선의 선택을 할 수 있다.

조건 1. 탐욕스러운 선택 조건 → 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 하며, 안전하다는 의미는 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.

조건 2. 최적 부분 구조 조건 → 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적의 해결 방법이어야 한다.

따라서 위 2개의 조건을 만족하는 문제에서 그리디 알고리즘을 사용하면 최종 결과가 최적의 해결 결과가 되므로, 순간의 선택이 최선이 된다.

 

활용 예시

• 동전 거스름돈(특정 금액의 최소한의 동전 개수 구하기)
• 최소 신장 트리(Prim 알고리즘)
• 최단 경로 찾기(Dijkstra 알고리즘)