<알고리즘> 그리디 알고리즘 (Greedy, 탐욕 알고리즘)

그리디 알고리즘 이란?

탐욕 알고리즘이라는 뜻으로 항상 최적의 해를 구하는 알고리즘이다. 작은 규모의 문제에서 답을 구할 때 항상 최적의 값을 선택하여 진행한다. 이러한 최적의 값들이 모여서 최종적으로 답이 만들어진다. 따라서 해당 알고리즘을 사용하는 것은 순간마다의 최적의 해를 골랐다고 해서 그것이 모아진 최종적인 답이 최적의 답이라는 보장은 없다. 그러므로 그리디 알고리즘을 사용하는 경우는 지역적으로 최적이면서 전역적으로도 최적인 문제에 사용하는 것이 효과적이다.

 

만약에 가장 큰 값을 찾아야하는 문제가 있다고 하자. 이때 숫자들은 트리구조에 저장되어 있다고 한다면 그리디 알고리즘을 사용한다고 가장 최적의 답이 구해진다고 장담 할 수는 없다. 중간 계층에서 최적의 해를 고르는 경우 가장 밑의 자식 노드에서 max값을 무조건 고른다고 볼 수는 없다. 따라서 그리디 알고리즘을 사용하는 경우 문제에 대한 해석과 분석이 중요하다고 볼 수 있다.

 

---

 

그리디 알고리즘의 사용 조건

그리디 알고리즘의 사용 조건에는 두가지가 있다. 첫번째로는 탐욕스런 선택 조건(Greedy choice property)와 두번째로는 최적 부분 구조 조건(Optimal substructure)이다. 해당 조건들을 만족하면 그리디 알고리즘을 사용하는 것이 권장된다. 하지만 해당 조건에 부합하지 않는다고 알고리즘을 사용하지 않는 것은 아니다. 빠르게 최적의 근사치에 대한 해를 얻기 위해서 알고리즘을 사용하기도 한다.

 

🔎탐욕스런 선택 조건(Greedy choice property):
앞선 선택의 결과가 이후의 사건에 대한 선택에 영향을 미치지 않는다.

🔎최적 부분 구조 조건(Optimal substructure):
작은 문제에 대한 최적의 해를 구하는 방법이 최종의 해를 구하는 방법과 동일하다.

---

 

그리디 vs 다이나믹 프로그래밍

다이나믹 프로그래밍, 즉 DP 알고리즘은 항상 최적의 해를 구할 수 있다는 장점이 있지만 그리디 알고리즘에 비해서 시간이 더 소모되고 메모리 또한 사용된다는 점이 있다. 반면 그리디 알고리즘은 빠른 시간내에 최적의 해에 근접한 답을 얻을 수 있다는 장점이 있다. 하지만 DP알고리즘과는 다르게 항상 최적의 해를 구할 수는 없다. 따라서 문제의 해석에 따라서 어떤 알고리즘을 사용하는지 결정하고 사용해야 한다.

 

또한 DP알고리즘은 중복문제에 대한 해결이 가능하다. 하지만 그리디 알고리즘은 중복 문제에 대한 해결이 가능하지 않다. DP는 문제가 중복되는 경우가 많아서 해당 중복 문제에 대한 해결이 필요하지만 그리디 알고리즘은 최종 해를 구하기 위해서 한번의 계산 과정만이 필요하기에 중복 문제가 존재하더라도 효과적으로 과정을 줄이는 방법이 효율적으로 처리되지 않는다.

 

 

참고:

https://wnehgus101.tistory.com/entry/알고리즘-동적-계획법-DP-Dynamic-Programming

<알고리즘> 동적 계획법 (DP: Dynamic Programming)

 

https://adjh54.tistory.com/212

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기