Greedy (탐욕) 알고리즘

그리디 알고리즘이란?

매 순간 최선의 방법(탐욕적인) 방법을 선택하는 알고리즘. 전체적으로 봤을 때도 최적의 선택인지 알 수 없으므로 특정 조건 하에 써야 한다. 계산속도가 빠르다는 장점이 있다.

어떤 상황에서 쓸 수 있을까?

1. 탐욕 선택 속성: 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때

2. 최적 부분 구조: 부분 문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때