[개념정리] 그리디

그리디(Greedy)란?

문제를 해결할 때 각 단계에서 가장 최적인 선택을 하여 최종적인 해를 구하는 알고리즘입니다.

이 알고리즘은 각 선택이 가장 좋은 선택이라고 믿고, 그 선택이 나중에 어떤 영향을 미칠지 고려하지 않습니다. 즉, 그 순간에 최적이라고 생각되는 답을 선택하는 방식입니다.

그리디 알고리즘은 항상 최적의 해를 보장하지는 않지만, 특정 조건 하에서는 매우 효율적으로 작동합니다.

 

그리디 알고리즘의 특징

1. 부분 최적 해: 그리디 알고리즘은 각 단계에서 최적인 선택을 하는데, 이것이 전체 문제의 최적 해를 보장하는 것은 아닙니다.
2. 근사 해: 그리디 알고리즘은 때로는 전체 최적 해를 구하지 못하고 근사적인 해를 구하는 경우가 많습니다. 이 때문에 그리디 알고리즘은 최적화 문제에서 "근사 알고리즘"으로 분류되기도 합니다.
3. 문제의 구조가 중요: 그리디 알고리즘이 최적의 해를 보장할 수 있는 경우는 문제의 구조에 따라 다릅니다. 이를 위해서는 현재의 최적 선택이 미래에 미치는 영향이 없어야 하며, 부분적으로 최적의 선택이 전체적으로 최적의 해를 만든다는 특성을 가질 때 사용이 적합합니다.

 

그리디 알고리즘을 사용할 수 있는 경우

그리디 알고리즘은 특정 문제에서 최적의 해를 찾을 수 있습니다.

1. 현재 선택이 미래 선택에 영향을 미치지 않는 경우
2. 그리디 알고리즘을 사용해도 전체 최적 해를 찾을 수 있는 경우입니다. 예를 들어, 동전 문제에서 주어진 금액을 가장 적은 동전으로 만드는 경우, 각 동전을 선택할 때 선택된 동전이 미래의 선택에 영향을 미치지 않기 때문에 최적의 해를 구할 수 있습니다.
3. 부분 최적 해가 모이면 전체 최적 해가 되는 경우
4. 부분 문제에서 최적의 해가 전체 문제의 최적 해를 만들어낼 때, 그리디 알고리즘이 최적의 해를 찾습니다. 예를 들어, 크루스칼 알고리즘이나 프림 알고리즘처럼 최소 신장 트리를 만들 때, 각 선택이 부분적으로 최적이지만 그 결과가 전체적인 최적 해를 형성합니다.

 

그리디 알고리즘의 예시

1. 동전 교환 문제
2. 주어진 금액을 최소한의 동전으로 바꾸는 문제에서 그리디 알고리즘을 사용할 수 있습니다. 예를 들어, 1원, 5원, 10원, 50원, 100원 동전이 있을 때, 268원을 만들려면 100원 동전 2개, 50원 동전 1개, 10원 동전 1개, 5원 동전 1개, 1원 동전 3개를 선택하는 방식입니다. 각 단계에서 가장 큰 동전을 선택하고, 나머지를 그에 맞게 선택하는 방식입니다.
3. 최소 신장 트리(MST)
4. 크루스칼 알고리즘과 프림 알고리즘은 그리디 알고리즘을 사용하여 최소 신장 트리를 찾는 대표적인 예입니다. 크루스칼 알고리즘은 가장 작은 간선부터 차례대로 선택하여 최소 신장 트리를 만들고, 프림 알고리즘은 시작 정점에서부터 가장 가까운 간선을 선택하여 MST를 완성합니다.
5. 활동 선택 문제
6. 활동 선택 문제에서는 주어진 활동들을 겹치지 않게 선택하는 방법을 묻습니다. 그리디 알고리즘은 종료 시간이 가장 빠른 활동부터 선택하는 방식으로 문제를 해결할 수 있습니다.

그리디 알고리즘의 한계

그리디 알고리즘이 항상 최적의 해를 제공하는 것은 아닙니다. 예를 들어, 배낭 문제나 최단 경로 문제와 같은 경우에서는 그리디 알고리즘이 최적 해를 구하지 못할 수 있습니다. 이러한 문제들은 그리디 알고리즘 대신 동적 계획법이나 다익스트라 알고리즘 같은 다른 알고리즘을 사용해야 합니다.

 

그리디 알고리즘 구현 방법

1. 문제의 탐욕적 속성 확인
   • 현재 단계에서 최적의 선택을 하는 것이 전체 최적 해로 이어지는지 확인합니다.
   • 즉, 부분 최적 해의 조합이 전체 최적 해를 보장해야 합니다.
2. 현재 선택이 미래에 영향을 주지 않는지 확인
   • 현재 단계에서의 최적 선택이 이후 선택에 영향을 주지 않아야 합니다.
3. 그리디 선택 기준 정의
   • 매 단계에서 어떤 기준으로 최적의 선택을 할 것인지 정합니다.
   • 예를 들어, 가장 작은 값, 가장 큰 값, 최소 비용 등을 기준으로 선택할 수 있습니다.
4. 정렬(필요할 경우)
   • 대부분의 그리디 알고리즘은 특정 기준으로 데이터를 정렬한 후 처리합니다.
5. 반복문을 사용하여 선택 수행
   • 각 단계에서 가장 최적인 선택을 반복적으로 수행하면서 문제를 해결합니다.