탐욕 알고리즘 (그리디 알고리즘) 뜻

탐욕 알고리즘 (그리디 알고리즘) 뜻

 

탐욕 알고리즘 (=혹은 그리디 알고리즘, greedy algorithm)이라 최적의 결과를 구하기 위해 근사치를 사용하는 방법으로, 여러 가지 경우 중 하나를 결정해야 할때, 먼 미래가 아닌 그때그때 순간에 최적이라고 생각되는 경우를 선택해 나가는 방식의 알고리즘을 뜻합니다.

 

 

따라서 탐욕 알고리즘은 그때그때의 선택은 지역적인 의미로써는 최적이지만, 모든 선택을 마치고 최종적인 해답을 만들었을때 해당 답이 최적이라고는 보장할 수 없습니다.

 

반대로 다음의 특정 조건들이 성립했을때 탐욕 알고리즘이 최적해를 구할 수 있는데, 1) 탐욕스런 선택 조건 (greedy choice property)과 2) 최적 부분 구조 조건(optimal substructure)이라는 두 조건이 모두 성립할 경우에는 탐욕 알고리즘으로 빠르게 최적해를 구할 수 있습니다.

 

다만 위의 조건이 성립하지 않기 때문에 최적해를 구할 수 없더라도 탐욕 알고리즘이 대부분 계산 속도가 빠르기 때문에 근사 알고리즘으로써 실용적인 목적으로 사용할 수 있습니다.