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

 

 

 

📌 그리디 알고리즘이란?

매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘

그러나 그리디 알고리즘은 전체에서 최적의 값을 언제나 구할 수는 없다. 

 

예를 하나 들어보자

실제 최단 경로와 그리디 알고리즘의 경로

그리디 알고리즘(Greedy Algorithm)에서 경로를 선택할 때는 선택하는 순간의 최적 값을 찾는다. 그러니까 B, C, D를 선택하는 순간에서는 C 경로인 A, C, E를 고르게 된다. 그러나 실제 최단 경로는 A, D, E다. 이처럼 선택의 순간 그리디 알고리즘에 의해 최적의 값을 선택했지만 전체 선택에 대해서는 최적이 아닌 경로를 선택하게 된 꼴이다. 그리디 알고리즘은 경우의 수를 검증하는 백 트랙킹(Backtracking)을 하지 않기 때문에 전체 문제에서 항상 최적의 값을 구하지는 못한다.

 

📌 그리디 알고리즘을 사용하기 위한 2가지 조건

탐욕 선택 속성(Greedy Choice Property)

• 이전의 선택이 이후에 영향을 주지 않아야 한다.

최적 부분 구조(Optimal Substructure)

• 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다.

 

📌 그리디 알고리즘 사용처

활동 선택 문제(Action Selection Problem)

• N개의 활동에서 각 활동에 대해 시작 시간 및 종료 시간이 주어질 때, 한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제이다.

거스름돈 문제

• 돈을 받은 뒤 거스름돈을 최소 개수의 동전 및 지페의 조합으로 거스름돈을 주는 경우, 그 최소 개수를 구하는 문제이다.

최소 비용 신장 트리(Minimum spanning tree)

• 신장 트리는 그래프에서 모든 정점(상태 혹은 객체, Vertex)에 대한 최소한의 연결만을 남긴 그래프로, 최소 비용 신장 트리는 이러한 신장 트리들 중에 간선(선, Edge)의 가중치 합이 가장 작은 트리를 의미한다.