![[[NOTE 4] 그리디 알고리즘.pdf]]
| 일자 | 계획 | 진행상황 |
| --------- | ---------------------------------------- | ---- |
| 3/29 | 그리디 알고리즘, 동전 거스름돈 문제 | 💻 |
| 3/30 | week 1 리뷰 포인트 정리 및 옵시디언 업데이트, 이전 내용 리팩터링 | 💻 |
| 4/30, 5/1 | 최소 신장 트리 | 📓 |
| 5/2 | 최단 경로 찾기 | ✘ |
| 5/3 | 부분 배낭 문제 | ✘ |
| 5/4 | 집합 커버 문제 | ✘ |
| 5/5 | 작업 스케줄링 문제 | ✘ |
| 5/6 | 허프만 압축 | ✘ |
# 0. 그리디 알고리즘
## 0.1. 정의
- optimization problem을 해결하는 알고리즘
- optimization problem: 가능한 해들 중에서 가장 좋은 (최대 or 최소) 해를 찾는 문제
- (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 '욕심 내어' 최소값 또는 최대값을 가진 데이터를 선택
- 근시안적인 선택이라고 말하기도 함
- 일단 한 번 선택하면, 이를 절대로 번복하지 않음
- 이러한 특성 때문에 대부분의 그리디 알고리즘들은 매우 단순하며, 또한 제한적인 문제만이 그리디 알고리즘으로 해결됨.
# 1. 동전 거스름돈 문제 (Coin Change)
## 1.1 정의
- Coin Change 문제를 해결하는 가장 간단하고 효율적인 방법
- 남은 액수를 초과하지 않는 조건 하에 '욕심 내어' 가장 큰 액면의 동전을 취하는 것
- 500, 100, 10, 1원으로
## 1.2 알고리즘
```pseudo
CoinChange
입력: 거스름돈 액수 W
출력: 거스름돈 액수에 대한 최소 동전 수
1. change = W, n500 = n100 = n50 = n10 = n1 = 0 // 각 동전 개수
2. while (change ≥ 500)
change = change - 500, n500++ // 500원 동전 수 증가
3. while (change ≥ 100)
change = change - 100, n100++ // 100원 동전 수 증가
4. while (change ≥ 50)
change = change - 50, n50++ // 50원 동전 수 증가
5. while (change ≥ 10)
change = change - 10, n10++ // 10원 동전 수 증가
6. while (change ≥ 1)
change = change - 1, n1++ // 1원 동전 수 증가
7. return (n500 + n100 + n50 + n10 + n1) // 총 동전 수
```
## 1.3 특성
- 그리디 알고리즘의 근시안적 특성이 잘 드러남
- 거스름돈 change에 대해 가장 높은 액면의 동전을 거스르며, 500원 동전을 처리하는 `Line 2`에서는 100, 50, 10, 1원 동전을 몇 개씩 거슬러 주어야 할지에 대해서는 전혀 고려하지 않음.
## 1.4 문제점
- 160원 동전이 발행되면, 항상 최소 동전 수를 계산할 수 없음.
- 그러나 실제로는 그리디 알고리즘이 적용되도록 발행됨.
## 1.5 FSharp 구현
# 2. 최소 신장 트리 (Minimum Spanning Tree, MST)
## 2.1 개념
- 주어진 가중치 그래프에서 '사이클'이 없이 모든 점들을 연결시킨 트리들 **중** 간선들의 가중치 합이 **최소인** 트리
- 주어진 그래프의 신장 트리를 찾는 법: 사이클이 **없도록** 모든 점을 연결시킨다
- 그래프의 점의 수 $= n$일 때,
- 신장 트리에는 정확히 $(n-1)$개의 간선이 있다.
- 트리에 간선을 하나 추가하면, 반드시 사이클이 만들어진다.
## 2.2 알고리즘 종류
1. `Kruskal` 가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 '욕심 내어' 그 간선을 추가
2. `Prim` 임의의 점 하나를 선택한 후, $(n-1)$개의 간선을 하나씩 추가. 추가되는 간선은 만들어진 트리에 연결시킬 때 '욕심 내어' 항상 최소의 가중치로 연결되는 간선.
> 알고리즘의 입력은 1개의 연결 성분(connected component)으로 된 가중치 그래프
## 2.3 Kruskal 알고리즘
```pseudo
KruskalMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 간선들을 정렬: L = 정렬된 간선 리스트
2. T = ∅ // 트리 T를 초기화
3. while ( T의 간선 수 < n-1 )
4. L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거
5. if (간선 e가 T에 추가되어 사이클을 만들지 않으면)
6. e를 T에 추가
7. else // e가 T에 추가되어 사이클이 생기는 경우
8. e를 버린다.
9. return 트리 T // T는 최소 신장 트리
```
### 2.3.1 수행 과정
![[스크린샷 2026-03-31 오후 8.34.46.png]]
### 2.3.2 시간 복잡도
- `Line 1` 간선 정렬하는 데 $O(m \log m)$. $m$은 입력 그래프에 있는 간선의 수
- `Line 2` T를 초기화하는 것이므로 $O(1)$시간
- `Line 3-8`
- while-루프는 최대 $m$번 수행
- 그래프의 모든 간선이 while-루프 내에서 처리되는 경우
- while-루프 내에서는 $L$로부터 가져온 간선 $e$가 사이클을 만드는지를 검사하는 데 거의 $O(1)$시간.
- 따라서 **최종 시간복잡도**: $O(m \log m)$
## 2.4 Prim 알고리즘
```pseudo
PrimMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 최소 신장 트리 T
1. G에서 임의의 점 p를 시작점으로 선택 D[p] = 0
// D[v]는 T에 있는 u와 v를 연결하는 간선의 최소 가중치를 저장하기 위한 원소
2. for (점 p가 아닌 각 점 v에 대하여) // 배열 D의 초기화
3. if (간선 (p, v)가 그래프에 있으면)
4. D[v] = 간선 (p, v)의 가중치
5. else
6. D[v] = ∞
7. T = {p} // 초기에 트리 T는 점 p만을 가진다.
8. while (T에 있는 점의 수 < n) {
9. T에 속하지 않은 각 점 v에 대하여,
10. D[v]가 최소인 점 vmin과 연결된 간선 (u, vmin)을 T에 추가,
11. 여기서 u는 T에 속한 점이고, 점 vmin도 T에 추가
12. for (T에 속하지 않은 각 점 w에 대해서)
13. if (간선 (vmin, w)의 가중치 < D[w])
14. D[w] = 간선 (vmin, w)의 가중치 // D[w]를 갱신
15. }
16. return T // T는 최소 신장 트리
```
### 2.4.1 D\[v\] 설명
- `Line 1`
- 임의로 점 $p$를 선택하고, $D[p]=0$으로 놓는다.
- $D[v]$에는 점 $v$와 $T$에 속한 점들을 연결하는 간선들 중에서 최소 가중치를 가진 간선의 가중치를 저장.
### 2.4.2 수행 과정
- `Line 1` 임의의 점 $c$ 선택, $D[c]=0$으로 초기화
- `Line 2-6`
- 시작점 $c$와 간선으로 연결된 각 점 $v$에 대해서, $D[v]$를 각 간선의 가중치로 초기화
- 나머지 각 점 $v$에 대해서, $D[v]$는 $\infty$ 로 초기화
- `Line 7` $T = \{c\}$로 초기화
- `Line 8-9` $T$에 가장 가까운 점 $b$를 추가
- $b$에 연결된 애들 $D$도 갱신하고,
- 또 $T$에 가장 가까운 점 추가
- 반복
### 2.4.3 Prim 알고리즘이 찾은 $T$에는 왜 사이클이 없을까?
- 항상 $T$ 밖에 있는 점을 추가하므로 사이클이 만들어지지 않음 (더 찾아보기)
### 2.4.4 시간 복잡도
- while-루프가 $(n-1)$회 반복되고,
- $1$회 반복 시에 `Line 9`에서 $T$에 속하지 않은 각 점 $v$에 대하여, $D[v]$가 최소인 점 $v_{min}$을 찾는 데 $O(n)$시간 소요
- 배열 $D$에서 (현재 $T$에 속하지 않은 점들에 대해서) 최솟값을 찾는 것이고, 배열의 크기는 $n$이기 때문
- 따라서 최종 시간복잡도: $(n-1) \times O(n) = O(n^2)$
- Binary Heap(최소 힙)을 사용하여 $v_{min}$을 찾으면 $O(m \log n)$, $m$은 간선 수. 따라서 간선 수가 $O(n)$이면 $O(n \log n)$.
## 2.5 Kruskal과 Prim의 수행 과정 비교
1. `Kruskal`
1. 간선이 1개씩 T에 추가되는데, 이는 마치 n개의 점들이 각각의 트리인 상태에서 간선이 추가되면 2개의 트리가 1개의 트리로 합쳐지는 것과 같음
2. 이를 반복해 1개의 트리인 T를 생성
3. 즉, n개의 트리들이 점차 합쳐져 1개의 신장 트리가 만들어진다.
2. `Prim`
1. T가 점 1개인 트리에서 시작되어 간선을 1개씩 추가
2. 1개의 트리가 자라나서 신장 트리가 된다.
# 3. 최단 경로 찾기
# 4. 부분 배낭 문제
# 5. 집합 커버 문제
# 6. 작업 스케줄링 문제
# 7. 허프만 압축