[자료구조/알고리즘] 탐욕 알고리즘 Greedy

[탐욕 알고리즘이란?]

Greedy : 탐욕스러운, 욕심 많은

Greedy Algorithm : 매 순간 최적이라고 생각하는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

 

[해결 방법]

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택

2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 과정을 반복함

 

[특정한 상황] - 최적의 해를 보장받기 위한 조건

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

: 앞의 선택이 이후 선택에 영향을 주지 않음

2. 최적 부분 구조(Optinal Substructure)

: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

 

* 최적의 결과를 도출하는 것이 아닐 수 있지만 어느정도 근사값 도출이 가능함