그리디 알고리즘(Greedy Algorithm) 이란?

그리디 알고리즘은 탐욕 알고리즘이라고도 불리며, 현재 상황에서

가장 최적이라고 생각되는 선택을 하는 방식으로 문제를 해결하는 알고리즘이다.

즉, 각 단계에서 지금 당장 가장 좋아 보이는 선택을 반복함으로써 최종 해답에 도달하는 방식이다.

그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고,

그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다.

이 알고리즘이 잘 작동하기 위한 2가지 중요한 속성이 있다.

  1. 탐욕적 선택 속성(Greedy Choice Property)

각 단계에서 내린 탐욕적인 선택이 최종 해답을 찾는데 영향을 미치지 않으며,

오히려 최적의 전체 해답을 찾는데 기여한다는 속성이다.

즉, 지역적인 최적해가 전역적인 최적해로 이어져야 한다.

  1. 최적 부분 구조(Optimal Substructure)

매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 한다.

장점