[알고리즘 개념정리]Greedy Algorithm(욕심쟁이 알고리즘, 탐욕 알고리즘,탐욕법)

Greedy Algorithm(욕심쟁이 알고리즘, 탐욕 알고리즘,탐욕법)

 

그리디 알고리즘이란?

그리디 알고리즘이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

 

주의할 점은 지금 당장 최적의 선택이라고 해도 결과적으로는 최선의 결과가 아닐 수 있다.

즉, 그리디 알고리즘은' 되는가'를 확인하거나 '적당한 결과'를 도출해내는 알고리즘이라 생각할 수 있다.

 

 

그리디 알고리즘을 사용하기에 적절한 문제는,

  -탐욕 선택 속성(greedy choice property)

  -최적 부분 구조(optimal substructure)의 특성을 가지는 문제들을 해결하기에 좋다.

즉, 1) 한번의 선택이 다음 선택에는 전혀 무관한 값 2) 매 순간의 최적해가 문제에 대한 최적

이 두가지 조건을 충족해야지 그리디 알고리즘을 사용하기에 좋다.

 

 

예시

-적절한 예시

가장 단 기간에 서울애서 부산까지 도착하는 거리를 구하려면 그 순간 순간 가장 빠른 최단 경로를 구하면 된다.

즉, 서울에서 대구까지의 최적의 거리, 대구에서 부산까지의 최적의 거리를 구하는 것이 그리디 알고리즘이라고 할 수 있다.

 

 

 

-안 좋은 예시

출처 : https://besjournals.onlinelibrary.wiley.com/doi/full/10.1111/1365-2656.12963

이와 같은 트리가 있을 때, 각 성분의 합이 최대가 되는 값을 구한다고 해보자

그리디 알고리즘은 각 순간에서 최적의 답을 고르게 된다.

그래서 두번째 트리를 보면 순간 순간의 선택이 제일 크지만, 막상 결과는 가장 최선이 아닐 수 있다.

이런 순간에는 전체 탐색 후에 최선의 결과를 구하는 것이 속도는 느리지만 해답이 될 수 있다.

 

 

참고 : https://namu.wiki/w/그리디 알고리즘