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

그리디 알고리즘(Greedy Algorithm)이란 문제를 해결하는 과정에서 순간 순간마다 최선이라고 생각하는 것을 선택하여

최종 해답에 도달하는 알고리즘을 의미한다. 계산 과정이 굉장히 빠른 알고리즘이지만, 순간 순간 마다의 최선의 선택이

언제나 전체 결과의 최선의 해결책을 보장하지는 않는다는 단점이 있다.

 

그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야 한다.

1. 최적 부분 구조(Optimal Substructure)
  : 부분 문제의 최적 결과를 전체에 그대로 적용할 수 있다.
2. 탐욕적 선택 속성(Greedy Choice Property)
  : 이전의 선택이 이후 선택에 영향을 주지 않는다.