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

1.그리디 알고리즘 이란?

목적을 도달하기 위한 선택의 순간에 최고의 선택만 하는게 그리디 알고리즘 입니다.

탐욕법이라고도 합니다.

그림으로 나타내면 다음과 같습니다.

 

A시작 D목표 일때

최단 경로는 A->C->D 입니다.

하지만 그리디 알고리즘은 매 선택의 순간에 최고의 선택을 하기때문에

A->C로 가지않고 A->B로 가게됩니다.

이것이 그리디 알고리즘 입니다.

따라서 항상 최적의해를 찾게되는 알고리즘은 아닙니다.