[알고리즘] 그리디 알고리즘 (Greedy Alogrithm)

 

 

 

그리디 알고리즘이란?

• 말 그대로 탐욕스러운, 욕심 많은 알고리즘
• 다익스트라 알고리즘의 기반이 되는 알고리즘
• 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달
• 지역적으로는 최적일 수 있지만, 그 선택들을 계속 수집한다고 전역적으로 최적임을 보장 못함
• 하지만 탐욕 알고리즘을 푸는 문제들은 지역적 최적 = 전역적 최적 임을 보장! 

 

그리디 알고리즘 동작 방식

 

1. 선택 절차

현재 상태에서 최적의 해답을 선택

 

2. 적절성 검사

선택된 해가 문제의 조건을 만족하는 지 검사

 

3. 해답 검사

원래의 문제가 해결되었는지 검사 -> 해결되지 않았다면 선택 절차로 돌아가서 다시 반복

 

그리디를 사용하기 위해 필요한 조건

 

1. 탐욕적 선택 속성

앞의 선택이 이후의 선택에 영향을 주지 않는다.

 

2. 최적 부분 구조

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

 

위 조건이 성립하지 않으면, 최적해를 구하지 못한다. 하지만 계산 속도가 빠르기 때문에 가장 최적인 답을 찾지 않아도 근사해를 찾는 "근사 알고리즘"으로 사용이 가능하다. 

---

출처

겐지충 프로그래머 :: 알고리즘 - 그리디 알고리즘(Greedy Algorithm) (tistory.com)

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

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬 (hanamon.kr)

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

탐욕법(그리디) 알고리즘 (velog.io)

탐욕법(그리디) 알고리즘