그리디 알고리즘 / Greedy Algorithm / 탐욕법

*️⃣  개념

• Greedy: 탐욕스러운, 욕심 많은
• 그리디 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
• 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표

 

*️⃣  그리디 알고리즘 적용 조건

1. 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

 

*️⃣  그리디 알고리즘 문제 해결 방법

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

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

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

 

 

#️⃣  그리디 알고리즘 응용 문제

https://www.acmicpc.net/workbook/view/4380

 

 

 

 

ℹ️  그리디 알고리즘 VS 동적 계획법 

 

 

 

참고: https://adjh54.tistory.com/212