[2021 하계 모각코] 2차시

그리디 알고리즘

---

그리디 알고리즘은 최적해를 구하는 상황에서 사용하는 알고리즘으로 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 생각하는 것을 선택하는 알고리즘이다. 즉 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 것이다. 따라서 탐욕 알고리즘이라고도 한다.

​

최적화 문제에서 동적 프로그래밍 사용 시 지나치게 많은 일을 하기 때문에 착안된 알고리즘이다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.

각 단계의 최적해를 선택하기 때문에 전체 최적해를 보장해주지 않는다.

​

대표적인 예제로 거스름돈, 활동 선택 문제, 분할 가능 배낭문제가 있다.

​

​

ex> 거스름돈

​

: 주어진 금액에 대해 최소 개수의 동전으로 거스름돈을 거슬러 준다.

​

알고리즘 : 가장 가치가 높은 동전을 우선으로 거스름돈을 구성한다.

​

하지만 만약 1200원을 거슬러준다고 할 때 500원, 100원 동전만이 아니라 400원 동전도 포함된다면 최적해는 400원 동전 3개이지만 그리디 알고리즘의 방식으로는 500원 2개, 100원 2개를 거슬러주게 된다.

즉 그리디 알고리즘은 항상 최적해를 보장하지 않는다.

​

https://github.com/miraekwak/BOJ/blob/main/5585.py

GitHub - miraekwak/BOJ

---

 

최소비용 신장트리와 최단 경로의 알고리즘 역시 그리디 알고리즘 이다.

 

---

최소 비용 신장 트리

---

 

신장트리란 선(신장)에 비용이 부여되어 있는 트리를 말한다. 최소 비용 신장 트리란 신장 트리에서 최소 비용을 가지는 신장을 선택하여 모든 vertex가 연결되도록 하는 신장트리를 말한다.

이때 최소 신장 트리는 순환되어선 안된다. 즉 사이클이 발생할 수 없다.

​

최소 신장 트리를 구현하는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이 있다.

프림 알고리즘 : 정점을 선택하고 선택된 정점과 연결된 간선 중에 가장 적은 비용이 드는 간선의 다른 한 정점을 선택하는 방식이다. 이때 비용은 두 정점 사이의 비용만으로 비교한다.

크루스칼 알고리즘 : 전체 간선의 각 비용을 정렬하여 가장 적은 비용이 드는 간선을 선택해 나가는 방식이다.

이때 사이클이 발생하는 간선은 선택하지 않는다.

​

​

---

최단 경로

---

다익스트라 알고리즘을 사용하여 최단 경로 문제를 해결할 수 있다.

다익스트라 알고리즘은 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다.

즉 그래프 상의 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘이다. 이때 비용은 단순히 두 정점 사이의 비용으로 계산하는 것이 아니라 시작 노드로 부터의 다른 정점을 거치게 되는 비용이 최소라면 해당 비용으로 계산한다.

​

다익스트라 vs 프림

- 다익스트라는 시작 노드가 정해져 있다.

- 다익스트라는 다른 정점을 거쳐 정해지는 최소비용을 계산하지만 프림은 단순히 두 정점의 비용만을 계산한다.

​

최단 경로를 구하는 다른 알고리즘으로는 플로이드 워셜 알고리즘이 있다.

플로이드 워셜 알고리즘은 하나의 정점에서 출발해 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 모든 정점을 출발, 도착 정점으로 봄으로써 모든 정점에서 모든 정점으로의 최단경로를 다 구할 수 있다. 그래프 상의 정점간 비용으로 2차원 배열을 초기화한 후 거쳐가는 정점을 기준으로 알고리즘을 수행한다.

​

다익스트라 vs 플로이드 워셜

- 다익스트라는 시작노드가 정해져있지만 플로이드 워셜은 모든 정점이다.

- 다익스트라는 가장 적은 비용을 하나씩 선택했다면 플로이드 워셜은 거쳐가는 정점을 기준으로 계산한다.