---

개념

그리디 알고리즘(Greedy algorithm)은 최적해를 구하는 데 사용되는 알고리즘 중 하나입니다. 그리디 알고리즘은 각 단계에서 가장 좋은 선택을 하는 방식으로 동작합니다. 현재 상황에서 가장 유리한 선택을 하여 단계별로 해를 구성하고, 이를 모아서 최종적인 해답을 찾는 방식입니다.

그리디 알고리즘은 각 단계에서의 선택이 지역적으로는 최적일 수 있지만, 전체적으로는 최적해를 보장하지는 않습니다. 즉, 그리디 알고리즘이 항상 최적해를 구하는 것은 아닙니다. 그러나 그리디 알고리즘은 대부분의 경우에 유용하고 효과적입니다.

그리디 알고리즘은 실행 속도가 빠르고 간단한 구현이 가능하며, 근사해를 구하는 데에도 사용될 수 있습니다. 하지만 문제에 따라 그리디 알고리즘이 항상 올바른 해를 제공하지는 않으므로 주의가 필요합니다.

---

특징

각 단계에서 가장 최적인 선택을 하는 알고리즘입니다. 이러한 선택은 그 순간에는 지역적으로 최적인 선택이지만, 전역적으로 최적인 해결책을 보장하지는 않을 수 있습니다. 그리디 알고리즘의 특징은 다음과 같습니다.

1. 탐욕적 선택: 그리디 알고리즘은 각 단계에서 가장 최적인 선택을 합니다. 이 선택은 그 순간에서는 지역적으로 최적인 선택이며, 그 순간에서는 최선의 선택으로 보입니다.

2. 부분 최적해: 그리디 알고리즘은 각 단계에서 최적인 선택을 하기 때문에 부분적으로 최적인 해결책을 구성합니다. 각 단계에서 최적인 선택을 함으로써 전체 문제의 최적해에 도달할 수 있을지는 보장되지 않습니다.

3. 탐욕적 선택과 최적 부분 구조: 그리디 알고리즘은 문제를 작은 부분 문제로 분해하고, 각 부분 문제에 대해 탐욕적으로 선택하여 부분 문제의 최적해를 구합니다. 이렇게 구한 부분 해들을 결합하여 전체 문제의 최적해를 찾습니다.

4. 역할의 한계: 그리디 알고리즘이 항상 전역적으로 최적해를 보장하지는 않습니다. 때문에, 그리디 알고리즘이 항상 올바른 해결책을 제공하는 것은 아니며, 문제에 따라서는 최적해를 구하지 못할 수도 있습니다.

그리디 알고리즘은 실행 속도가 빠르고 구현이 간단한 장점이 있으며, 최적해를 보장하지 않더라도 근사해(Approximate Solution)를 구하는 데에 유용하게 사용될 수 있습니다. 그리디 알고리즘은 문제의 특성과 조건에 따라 적용 가능성이 다르므로, 각 문제에 맞는 알고리즘을 선택해야 합니다.

---

예시

1. 동전 거스름돈 문제: 거스름돈을 최소한의 동전 개수로 주는 문제입니다. 예를 들어, 1260원을 거슬러 줘야 할 때, 가능한 적은 동전 개수로 거슬러주는 방법을 찾습니다.

2. 회의실 배정 문제: 여러 개의 회의가 있는데, 각 회의는 시작시간과 종료시간이 주어집니다. 이 중 겹치지 않는 최대한 많은 회의를 선택하는 문제입니다.

3. 배낭 문제: 배낭에 담을 수 있는 최대 무게가 정해져 있고, 각 물건은 가치와 무게를 가지고 있습니다. 배낭에 넣을 수 있는 물건들의 조합으로 얻을 수 있는 최대 가치를 구하는 문제입니다.

4. 프림 알고리즘: 무방향 그래프에서 최소 신장 트리를 구하는 알고리즘입니다. 시작 정점부터 출발하여 인접한 정점 중 가장 작은 가중치의 간선을 선택하며 트리를 확장해 나갑니다.

5. 크루스칼 알고리즘: 무방향 그래프에서 최소 신장 트리를 구하는 알고리즘입니다. 가중치가 작은 간선부터 선택하여 사이클이 형성되지 않는 경우에만 추가합니다.

동전 거스름돈 문제(Coin Change Problem)

이 문제는 가장 적은 개수의 동전을 사용하여 지불해야 할 돈을 거슬러주는 문제입니다.
예를 들어, 동전의 단위가 500원, 100원, 50원, 10원이 있고, 거슬러줘야 할 돈이 1260원이라고 가정해봅시다. 그리디 알고리즘을 사용하면 가장 큰 단위의 동전부터 사용하여 거슬러줄 수 있습니다.

1. 가장 큰 단위의 동전인 500원을 사용하여 500원을 거슬러줍니다. 남은 돈은 760원입니다.
2. 다음으로 큰 단위의 동전인 500원을 사용할 수 없으므로, 100원을 사용하여 600원을 거슬러줍니다. 남은 돈은 660원입니다.
3. 다시 100원을 사용하여 500원을 거슬러줍니다. 남은 돈은 560원입니다.
4. 이번에는 100원을 사용하여 400원을 거슬러줍니다. 남은 돈은 360원입니다.
5. 100원을 한 번 더 사용하여 300원을 거슬러줍니다. 남은 돈은 260원입니다.
6. 100원을 세 번 사용하여 100원을 거슬러줍니다. 남은 돈은 60원입니다.
7. 마지막으로 50원을 사용하여 10원을 거슬러줍니다. 남은 돈은 10원입니다.

이렇게 최소 개수의 동전을 사용하여 1260원을 거슬러줄 수 있습니다. 이 예시에서는 가장 큰 단위의 동전부터 사용하는 것이 최적의 선택이었기 때문에 그리디 알고리즘이 적용됩니다.

크루스칼 알고리즘(Kruskal)

"최소 신장 트리 (Minimum Spanning Tree)"를 구하는 크루스칼(Kruskal) 알고리즘이 있습니다.

최소 신장 트리는 가중치가 있는 그래프에서 모든 정점을 포함하면서 그 가중치의 합이 최소가 되는 트리입니다. 크루스칼 알고리즘은 그리디 알고리즘의 대표적인 예시로, 다음과 같은 단계로 동작합니다

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
2. 가중치가 가장 작은 간선부터 시작하여 사이클이 형성되지 않는 경우에만 간선을 선택합니다.
3. 선택한 간선을 최소 신장 트리에 추가합니다.
4. 모든 정점이 최소 신장 트리에 포함될 때까지 위의 단계를 반복합니다.

크루스칼 알고리즘은 간선의 가중치를 기준으로 선택하는 것이 그리디적인 선택입니다. 각 단계에서 가장 작은 가중치를 가진 간선을 선택하며, 사이클이 형성되지 않는 경우에만 간선을 추가하는 것이 특징입니다. 이를 통해 최소 신장 트리를 구할 수 있습니다.

부분 배낭 문제(Fractional Knapsack Problem)

이 문제는 제한된 용량을 가진 배낭에 물건을 넣을 때, 각 물건의 가치와 무게가 주어졌을 때, 최대의 가치를 얻을 수 있는 방법을 찾는 문제입니다. 그리디 알고리즘을 사용하여 무게당 가치가 가장 높은 물건부터 배낭에 넣는 것이 최적의 선택이 되는 경우가 있습니다. 이렇게 선택하면 가치를 최대화할 수 있습니다.