목차
- 그리디 알고리즘이란?
- 그리디 알고리즘 정당성
- 그리디 알고리즘 종류
- 그리디 알고리즘 예시
- 그리디 알고리즘과 DP 비교
1. 그리디 알고리즘이란?
그리디 알고리즘은 현재 이 순간에서 가장 최적의 해를 선택하는 알고리즘이다. 앞으로 진행될 선택에 끼칠 영향을 고려하지 않고 매 순간 선택에서 현재가 항상 최적의 해를 가져야 하기 때문에, 욕심쟁이 알고리즘이라고도 부른다.
현재 문제에서 가질 수 있는 최적의 해를 선택하면 다음 부분적인 문제에 대한 선택이 이뤄진다. 다시 말해, Top-Down 방식으로 더 작은 문제에 대한 최적의 해를 선택하고, 한번 선택된 결정은 다시 번복할 수 없다. 이러한 이유로 부분 문제는 최적의 해를 가지지만, 모든 전체 문제에서 최적의 해를 가진다고 말할 수 없다.
2. 그리디 알고리즘 정당성
그리디 알고리즘을 사용해 문제를 해결하는 것이 최적의 해를 보장하는가에 대한 판단을 하는 기준이 존재하고, 이것을 그리디 알고리즘의 정당성이라고 한다. 탐욕적 선택 속성과 최적 부분 구조를 통해 문제가 정당성을 판단할 수 있다.
- 탐욕적 선택 속성 (Greedy Choice Property)
: 각 단계에서 내리는 결정들로 최적의 해를 구할 수 있다. - 최적 부분 구조 (Optimal Substructure)
: 다음에 올 문제는 현재 문제의 부분적인 문제이며, 전체적인 문제에 대한 최적의 해를 고려하지 않는다.
3. 그리디 알고리즘 종류
1) 크루스칼 알고리즘
- 최소 신장 트리, MST
- 그래프 내 모든 정점을 최소 가중치로 연결하는 알고리즘
- 모든 간선을 정렬해 작은 가중치부터 선택한다. 연결된 두 정점의 부모를 union-find로 확인해 사이클을 확인한다.
- 정렬에 가장 많은 시간이 소요되므로 시간복잡도는 퀵소트의 시간복잡도인 O(E logE)이다.
2) 프림 알고리즘
- 최소 신장 트리, MST
- 그래프 내 모든 정점을 최소 가중치로 연결하는 알고리즘
- 최소 우선순위 큐를 이용해 가중치가 가장 작은 간선을 뽑고, 배열로 이미 방문한 노드인지 확인한다.
- 우선순위 큐를 이용하는데 가장 많은 시간이 소요되므로 시간복잡도는 O(E logE)이다.
3) 다익스트라 알고리즘
- 하나의 정점에서 각 정점까지 도달하는데 최소 비용을 구하는 알고리즘 (= 단일 출발지 최단 경로, SSP)
- 가장 작은 가중치를 가지는 노드를 선택하고, 방문한 적 없는 노드거나 더 작은 가중치 합계를 가진다면 가중치 테이블을 갱신시키고 해당 노드를 큐에 넣는다.
- 우선순위 큐를 이용하는데 가장 많은 시간이 소요되므로 시간복잡도는 O(E logE)이다.
4) 허프만 코딩
- 자주 등장하는 문자는 짧은 비트로, 상대적으로 자주 등장하지 않는 문자는 긴 비트로 표현
- 문자의 출연 빈도 수에 따라 가변 길이 코드로 변환한다.
- 압축을 위해 사용되는 알고리즘이다.
| 크루스칼 | 프림 | 허프만코딩 | 다익스트라 | |
| 구분 | MST | MST | MST | SPP |
| 사용 | 그래프 | 그래프 | 문자열 | 그래프 |
| 구현 | 정렬과 union-find | 배열 혹은 우선순위 큐 | 이진 트리 | 배열 혹은 우선순위 큐 |
| 시간복잡도 | O(E logE) | 배열 : O(N^2) 우선순위 큐 : O(E logV) |
O(N logN) | 배열 : O(N^2) 우선순위 큐 : O(E logV) |
4. 그리디 알고리즘 예시
- 거스름돈 문제 : 거스름돈을 최소 개수의 동전의 개수로 주기
- 회의실 예약 : 가장 많이 회의실을 이용할 수 있는 방법 구하기
- 외판원 문제 : 모든 고객을 방문하는 최단 시간 구하기
https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
5. 그리디와 DP 비교
| 그리디 | DP | |
| 설명 | 현재 상태에서 가질 수 있는 최적의 해 선택 |
하위 문제에 대한 해를 기반으로 최적의 해 선택 |
| 방식 | Top-Down 방식 | Bottom-Up 방식 |
| 특징 | 부분적인 상황에서 최적의 해를 가짐 빠르고 코드가 쉬움 |
전체적인 상황에서 최적의 해를 가짐 느리고 복잡함 |
| 정당성 | 탐욕적 선택 속성 최적 부분 문제 |
중복 부분 문제 최적 부분 문제 |
댓글