[알고리즘] 그리디 알고리즘

그리디 알고리즘

욕망의 항아리

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"

그리디(Greedy)함?

Greedy : 탐욕스러운

 

탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 불리는 알고리즘

말 그대로 매 순간마다 미래를 생각하지 않고 가장 최선의 선택만을 하는 기법

 

하지만 그리디는 그 선택의 순간에서는 최선일지 몰라도 전체를 생각했을 때 최선의 수는 아닐 수 있다!

'마시멜로 실험'을 예시로 들 수 있는데 당장 눈 앞의 마시멜로를 먹게 될 경우 
추후 더 많은 양의 마시멜로를 포기하는 셈이 되어버린다!

 

따라서 그리디는 최적해들의 집합이 전체 문제의 답인 경우에만 적용할 수 있다.

혹은 정답이 아닌 정답에 가까운 근사치를 구할 때 사용하거나...

 

예제

그리디 알고리즘의 가장 유명한 예로는 먼저 거스름돈 문제가 있다.

말 그대로 가장 적은 수의 동전으로 거스름돈을 주는 문제인데

이와 같은 경우에는 줄 수 있는 동전 중 가장 큰 단위의 동전부터 바꿔주게 되면 해결이 되는 문제다.

 

+ 여기서 만약 동전 단위가 서로 배수가 아니라 [500, 400, 30, 10]  이런식이면 얘기가 달라진다.

 

 

그 다음으로는 '최적 부분 구조' 문제에 적용할 수 있는데

예를 들어 서울 - 수원 - 대전 - 부산을 모두 순서대로 거치는 최단 경로를 구하기 위해서는

각 도시 사이 경로마다 최단 경로(각 단계의 최적해)를 선택해서 합치면 되는 것이다.

 

허나 반대로 그리디를 적용할 수 없는 문제 중 가장 대표적인 예시로는

• 외판원 순회 문제
• 냅색(배낭 채우기) 문제

과 같은 문제들이 존재한다.