[알고리즘] 그리디 알고리즘이란?(Greedy Algorithms)

 

💡그리디 알고리즘(Greedy Algorithm) 

그리디 알고리즘이란 탐욕적인 알고리즘이라고도 하며, 
선택의 순간마다 당장 눈앞에 보이는 최적인 상황만을 쫓아 최종적인 해답에 도달하는 방법

 

 

 

- 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 

- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 것이다. 

 

 

그리디 알고리즘을 통해 구한 최적 해

최적 해

- 그리디 알고리즘은 순간 하는 선택은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종 해답을 만들었다고 해서 그것이 최적이라는 보장이 없다. 

 

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제를 풀 때 보통  "가장 큰 순서대로" 혹은 "가장 작은 순서대로" 같은 기준을 제시해준다. 

 

 

👌그리디 알고리즘 해결 방법 

1. 선택절차 : 현재상태에서 최적의 해답 선택 

2. 적절성 검사 : 선택된 해가 문제의 조건에 만족하는지 검사 

3. 해답 검사: 원래의 문제가 해결되었는지 검사 후 해결되지 않았다면 선택 절차로 돌아가 위의 과정 반복 

 

 

👌그리디 알고리즘의 2가지 조건 (탐욕스런 선택 조건, 최적 부분 구조 조건) 

1. 탐욕스런 선택 속성: 앞의 선택이 이후에 선택에 영향을 주지 않는다. 

2. 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분(지역적) 문제에 대한 최적 해결 방법을 구성된다. 

 

이 조건들이 만족할 시 그리디 알고리즘의 성립된다. 

 

 

 

 

---

📌 그리디 알고리즘 예시 

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

https://www.acmicpc.net/problem/1026

1026번: 보물