그리디 알고리즘(Greedy Algorithm)

 

서론

 

 

영단어 greedy의 의미는 "탐욕스럽다"이다.

 

 

 

즉, 그리디 알고리즘이란, 탐욕스러운 사람처럼

 

눈앞에 보이는 이익만 쫓아가는 알고리즘을 뜻한다.

 

그리디 알고리즘이란

 

 

 

위와 같은 트리 구조에서,

 

왼쪽 노드로 가는 것이 가장 좋은 경로이지만

 

당장의 탐욕스러움으로 오른쪽 노드로 가는 것.

 

이러한 트리 탐색 알고리즘을

 

그리디 알고리즘이라고 한다.

 

 

언제 사용할까?

 

그리디 알고리즘은

 

* 동전 개수를 최소로 사용하는 문제.

(가장 큰 금액의 동전을 많이 사용하면 된다)

 

* 도시락을 하나씩만 데울 수 있는데, 먹는 시간을 최소화해야 하는 문제. 

(먹는 데 가장 오래 걸리는 도시락부터 데우면 된다)

 

와 같은 문제에서 유용하게 쓰일 수 있다.