매 순간 가장 최적의 선택을 하는 방식으로 문제를 해결하는 알고리즘
⭐ Greedy algorithm의 특징
✅ 1. 현재 최선의 선택
그리디 알고리즘은 문제를 해결하는 동안 각 단계에서 가장 최적인 선택을 함
✅ 2. 전역적 최적해는 보장되지 않음
그리디 알고리즘은 각 단계에서 최적의 선택을 하지만, 그 선택들이 전체적으로 최적의 해를 보장하지 않음
✅ 3. 단계적 해결
문제를 작은 하위 문제로 나누고 각 하위 문제를 해결하면서 점진적으로 전체 문제를 해결함
✅ 4. 단일 선택
한 번 선택된 값은 변경되지 않으며, 후속 단계에서 그 값을 바꾸지 않음
❗Greedy algorithm의 구현
✅ 1. 정렬을 통한 구현
- 가장 많이 사용되는 구현 방식 중 하나
- ex) 크루스칼 알고리즘처럼 간선을 가중치 순으로 정렬하거나, 회의실 배정 문제처럼 종료 시간을 기준으로 정렬한 후 순서대로 선택하는 경우가 많음
✅ 2. 반복문을 통한 구현
- 보통 for 또는 while 반복문을 통해 각 단계마다 greedy 선택을 수행함.
- ex) 거스름돈 문제에서 동전의 종류를 순회하며 동전의 게수를 세는 방식
⚠️ Greedy algorithm의 장단점
✅ 장점
-
간단함: 복잡한 사고 과정 없이 현재 상황에서 가장 좋은 선택을 하기 때문에 알고리즘의 구현이 매우 쉽고 직관적임
-
효율성: 동적 계획법처럼 모든 경우의 수를 고려하지 않고, 한 번의 선택만 하기 때문에 실행 시간이 빠르며 메모리도 적게 사용
❌ 단점
-
최적의 해를 보장하지 않음: 가장 큰 단점은 매 순간의 최적 선택이 최종적으로 전체 문제의 최적 해를 보장하지 못할 수 있다는 점
-
적용 가능성 제한: 그리디 알고리즘이 항상 최적의 해를 보장하는 문제는 '탐욕적 선택 속성'과 '최적 부분 구조'라는 특정 조건을 만족해야만 함. 이 조건이 충족되지 않는 문제에는 적용하기 어려움.
📝 예제
500원, 100원, 50원, 10원 동전으로 거스름돈 N원을 최소한의 개수로 거슬러주는 방법
N = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += N // coin # 해당 동전으로 거슬러줄 수 있는 개수
N %= coin # 남은 금액
print(count) # 출력: 6🔎 Greedy algorithm의 주요 활용 예시
✅ 1. 거스름돈 문제
거스름돈을 줄 때 동전의 개수를 최소화하는 문제
-
동작 방식
- 가장 큰 단위의 동전부터 거슬러 주는 방법.
- 동전의 단위가 큰 것부터 작은 것으로 정렬되어 있다면, 매 순간 남은 금액에 대해 가장 큰 동전을 선택하는 것이 최적의 해 보장.
-
ex) 1260원을 거슬러줘야 할 때, 500원, 100원, 50원, 10원 동전이 있다면, 500원 2개, 100원 2개, 50원 1개, 10원 1개를 주게 됨.
✅ 2. 최소 신장 트리 (Minimum Spanning Tree, MST)
그래프의 모든 노드를 연결하면서 간선 가중치의 합이 최소가 되는 트리를 찾는 문제 (그래프에서 일부 간선을 선택해서 만든 트리)
-
동작 방식
- Kruskal algorithm 과 같이, 모든 간선을 가중치에 따라 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 선에서 가장 가중치가 낮은 간선부터 하나씩 추가하는 방식으로 해결
- 매 순간 가장 가중치가 낮은 간선을 선택하는 것이 최적의 해 보장
✅ 3. 최단 경로 문제
특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 문제
-
동작 방식
- Dijkstra algorithm은 매 단계마다 방문하지 않은 노드 중에서 시작점으로부터의 거리가 가장 짧은 노드를 선택하는 Greedy 방식 사용
- 가중치가 음수가 아닌 그래프에서 최적해를 찾아냄
✅ 4. Huffman Coding
데이터 압축에 사용되는 알고리즘으로, 문자의 빈도수를 기반으로 코드를 할당하여 압축률을 높이는 문제
-
동작 방식
- 등장 빈도가 가장 낮은 두 문자를 선택하여 이진 트리를 만들고, 이 과정을 반복하여 최종적인 코드 생성
- 가장 효율적인 압축 코드 만듦
