xtring.dev

탐욕 알고리즘. 그리디 알고리즘(Greedy Algorithm)이라고도 불리는 알고리즘에 대해서 알아보겠습니다.(이하 그리디 알고리즘이라고 부름) 그리디 알고리즘은 동적 프로그래밍(Dynamic Programming) 사용 시 지나치게 많은 처리를 한다는 것에 착안하여 고안된 알고리즘입니다. 동적 프로그래밍과 함께 상호보완하는 개념입니다. 그리디(탐욕) 알고리즘이라는 이름이 붙게 된 이유는 '미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법'이기 때문에 지어졌다고 합니다. 각 단계에서 최선의 선택을 하는 것이 결국 전체의 최선이길 바라는 알고리즘이죠. 모든 경우에서 그리디 알고리즘이 최대 효율을 만들어주지는 못합니다. 쉬운 예로 마시멜로 이야기와 함께 해보겠습니다. 지금 마시멜로우를 앞에 ..