[알고리즘] 4. 그리디 알고리즘 (1)

그리디 알고리즘

탐욕법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법입니다.
최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
정당성 분석이 중요합니다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
하지만 코테에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀도록 출제됩니다.

4.1 동전 거스름돈

CoinChange 알고리즘은 항상 최적의 답을 주지 못함 • 따라서 실제로는 거스름돈에 대한 그리디 알고리즘이 적용되도록 동전이 발행됩니다.

실제 문제) 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 주어야 할 돈 N은 항상 10의 배수이다.

count = 0
n = 1260

array = [500, 100, 50, 10]

for coin in array:
	count += n // coin
	n %= coin

4.2 최소 신장 트리

4.2.1 신장트리 (ST - Spanning Tree)

DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있습니다.
탐색 도중에 사용된 간선만 모으면 만들 수 있습니다.
하나의 그래프에는 많은 신장 트리가 존재할 수 있습니다.
Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안됩니다.
따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 합니다.

4.2.2 최소신장트리 (MST - Minimum Spanning Tree)

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아닙니다.
MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말합니다.
즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것입니다.

4.2.2 Kruskal MST

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
간선 선택을 기반으로 하는 알고리즘이다.
이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.

[과정]
1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 즉, 가장 낮은 가중치를 먼저 선택한다.
- 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

시간복잡도

- O(elog₂e)

4.2.3 Prim MST

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

정점 선택을 기반으로 하는 알고리즘이다.
이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

[과정]
1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
- 즉, 가장 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

[시간복잡도]

- O(n^2)

4.3 최단 경로 찾기

4.3.1 Dijkstra

모든 정점까지의 최단 경로 구하기

다익스트라 알고리즘은, 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘입니다.

다익스트라 알고리즘은 그 방식이 효율적이라 그래프가 큰 경우에도 사용 가능한 장점이 있습니다.

하지만, 그래프 내 간선의 가중치가 음수인 것이 하나라도 있다면 사용할 수가 없습니다.

ShortestPath(G, s){
  	  /*D[v] 무한대로 초기화*/
      D[s] = 0; 모든 D[v] = INTMAX;
      
      while(s부터의 최단거리 확정되지 않은 점 있을 때){
          확정 안 된 점 v에 대해 최소 D[v]인 점 v 선택;
          D[v] 확정;

          각 점 w, D[w] 최단거리 값으로 갱신;
      }
      
      return D;
  }

4.4 부분 배낭 문제

배낭(Knapsack) 문제는 n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있을 때, 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제입니다.

원래의 배낭 문제는 물건을 통째로 배낭에 넣어야 하는 것에 반해,
부분 배낭(Fractional Knapsack) 문제는 물건을 부분적으로 담는 것이 허용 됩니다.

부분 배낭 문제에서는 물건을 부분적으로 배낭에 담을 수 있으므로, 최적해을 위해서 ‘욕심을 내어’ 단위 무게당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣습니다.

그런데 만일 그 다음으로 값나가는 물건을 ‘통째로’ 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담도록 한다.

FractionalKnapsack
입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v
각 물건의 단위 무게당 가치를 계산.
물건들을 단위 무게당 가치를 기준으로 내림차순으로 정렬, 정렬된 물건 리스트를 S라고 한다.
L=∅, w=0, v=0 // L: 배낭에 담을 물건 리스트, w: 배낭에 담긴 물건들의 무게의 합, v: 배낭에 담긴 물건들의 가치의 합
S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다.
while((w + x의 무게)<=C){
  x를 L에 추가시킨다.
  w = w + x의 무게
  v = v + x의 가치
  x를 S에서 제거한다.
  S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다.
}
if ((C-w) > 0) { // 배낭에 물건을 부분적으로 더 담을 여유가 있으면
  물건 x를 (C-w)만큼만 L에 추가한다.
  v = v + (C-w)만큼의 x의 가치
}
return L, v

Reference

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

[알고리즘] Kruskal 알고리즘 이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

[알고리즘] Prim 알고리즘 이란 - Heee's Development Blog