알고리즘 - 그리디(Greedy)

그리디(Greedy)

---

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

장기적인 결과보다 즉각적인 이익을 우선시하여 미래의 영향을 고려하지 않고 현재 상황을 기반으로 결정을 내린다.

그리디 알고리즘을 사용하면서 조심해야 될 부분은 그리디 알고리즘은 항상 최적의 해를 보장하지 않는다는 것이다.

그리디 알고리즘을 사용할 때 잘 따져보지 않으면 반례가 생길 수 있으니 조심해서 접근해야 된다.

그리디 알고리즘을 적용하기 위해서는 두 가지 조건이 성립해야 한다.

 

1. 탐욕 선택 조건

그리디 알고리즘을 적용하기 위해서는 탐욕적인 선택 즉, 선택지 중에서 최선의 선택을 했을 경우 전체 문제의 최적해를 반드시 도출할 수 있어야 한다.

 

2. 최적 부분 구조 조건

전체 문제를 여러 문제로 분할했을 때 하나 하나의 작은 문제에 대해서 최적해가 도출되어야 한다.

 

그리디 알고리즘의 장단점

그리디 알고리즘의 장점

간단하고 이해하기 쉬움

그리디 알고리즘은 데이터 사이의 관계를 고려하지 않고 수행을 하게 된다. 또한 최선이라고 선택한 데이터는 절대로 바꾸지 않는다.

이러한 그리디 알고리즘만의 특성으로 인해 그리디 알고리즘은 매우 간단하면서도 단순하게 작성하고 이해할 수 있다.

 

빠른 실행 시간

다른 알고리즘에 비해서 빠른 실행 시간을 가지고 있다. 앞서 설명했던 장점과 비슷한 이유인데 데이터 사이의 관계나 선택한 데이터를 바꾸지 않는 특징으로 인해 최적의 선택지 단 하나만을 파고들면서 문제를 해결하여 빠른 실행 시간을 제공한다.

 

그리디 알고리즘의 단점

항상 최적은 아님

그리디 알고리즘에서 가장 치명적인 단점이 바로 최적을 보장해주지 않는 다는 것이다. 이러한 알고리즘을 근사 알고리즘이라 부르는데 무조건 최적해를 구할 수는 없지만 많은 경우에 최적해에 근접한 값을 구할 수 있다.

 

최적성을 증명하기 어려움

그리디는 항상 최적의 해를 보장하지 않기 때문에 최적성을 증명하기 어려울 수도 있다. 따라서 그리디 알고리즘을 적용할 수 있는지 신중한 분석이 필요하다.

 

입력 순서에 민감함

입력 순서에 따라서 그리디의 성능에 차이가 발생할 수 있다. 따라서 그리디 알고리즘을 적용하기 전 정렬을 진행해 주는 것이 보다 높은 정확성과 성능을 보여준다.

 

제한된 적용 가능

트리 구조에서 가장 큰 합을 구하는 문제가 있을 경우 그리디를 적용하기 어렵다. 따라서 이진 트리로 구조를 바꿔주는 추가적인 작업이 필요할 수 있다.

 

 

그리디 알고리즘 수행 과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.

 

그리디 알고리즘의 사용 사례

다익스트라 알고리즘

그래프에서 두 노드 사이의 최단 경로를 찾는 알고리즘으로 현재 노드에서 가능한 가장 짧은 가장자리를 반복적으로 선택하여 작동한다.

 

크루스칼 알고리즘

그래프의 최소 신장 트리를 찾는다. 순환을 생성하지 않는 최소 가중치를 갖는 가장자리를 반복적으로 선택하여 작동한다.

 

스케줄링 및 자원 할당

작업을 스케줄링 하거나 효율적인 방식으로 자원을 할당할 수 있다.