[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘 (Greedy Algorithm) 이란?

• 그리디 알고리즘은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황 만을 쫓아 최종적인 해답에 도달하는 방법입니다. 따라서 가장 직관적인 알고리즘 설계 패러다임 중 하나라고 볼 수 있습니다. 
• 여러 경우 중 하나를 결정할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.
• 그리디는 현재도 최적이면서 최종적으로도 최적인 문제들입니다. 따라서 현재 상황에서 최적인 해를 찾으면 됩니다.

 

탐욕 알고리즘 문제를 해결하는 방법

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

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

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

 

그리디 알고리즘 정당성 증명

탐욕 알고리즘의 정당성 증명은 일정한 패턴을 가집니다. 

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

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

 

백준 문제 번호 (추후 작성 예정)

 

 

 

 

 

참고 블로그

[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java)