전체 글

11-2. [C/C++] Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘 Dijkstra 알고리즘은 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 그래서 Dijkstra 알고리즘은 출발점이 정해져 있는 상황에 사용하기 적합하다. 다익스트라 알고리즘은 간선의 가중치 값 중 음수가 없을 때 정상적으로 동작한다. 현실의 길(간선)에는 음수 가중치가 없기 때문에 다익스트라 알고리즘은 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 "가장 비용이 적은 노드"를 선택해서 임의의 과정을 반복하기 때문이다. 다익스트라 알고리즘 (1) 출발 노드를 설정한다. (2) 최단 거리 테이블을 초기화한다. (3) 방문하지 않은 노드 중에서 최단 거리..

11-1. 가중치 그래프에서의 최단 경로

최단 경로란? 최단 경로(shortest path) 문제는 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 이때 간선의 가중치는 보통 비용이나 거리, 시간 등을 나타낸다. 지도를 가중치 그래프로 나타낸다고 하면, 지도의 각 지역들은 그래프의 정점을 나타내고 가중치(간선)는 어떤 지역에서 다른 지역으로 이동하는 거리를 의미한다. 일반적으로 지도에서 출발점과 도착점을 설정하면 최단 경로를 보여준다. 숭실대입구역에서 서울대입구역으로 가는 경로는 엄청나게 많겠지만, 최단 경로는 많지 않을 것이다. (경로 상의 가중치 합이 같은 경로가 여러 개 있을 수도 있음) 최단 경로 알고리즘 최단 경로를 구하는 대표 알고리즘으로는 Dijkstra와 Flo..

[C/C++] 백준 3584번 - 가장 가까운 공통 조상

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include using namespace std; #define endl '\n' #define SIZE 10001 int T, N; int parent[SIZE]; bool visited[SIZE]; void initInput() { cin >> T; } void solve() { while (T--) { int u, v; cin >> N; for (int i = 1; i > u >> v; parent[v..

10-5. [C/C++] MST를 위한 Prim 알고리즘

Prim 알고리즘 Prim 알고리즘은 하나의 정점에서부터 시작해 트리를 단계적으로 확장해나가는 방법이다. 처음에는 시작 정점만이 MST에 포함된다. 다음으로 지금까지 만들어진 MST에 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점을 선택하여 트리를 확장한다. 이 과정을 트리가 (n - 1)개의 간선을 가질 때까지 계속한다. Prim() (1) 그래프에서 시작 정점을 선택해 초기 MST를 만든다. (2) 현재 MST의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다. (3) 이 정점 v와 이때의 간선을 MST에 추가한다. (4) 모든 정점이 삽입될 때 까지 2번으로 이동한다. Kruskal 알고리즘이 간선을 중심으로 하는 알고리즘인데 비해 Prim 알고리즘은 정점을 중심..

10-4. [C/C++] MST를 위한 Kruskal 알고리즘

Kruskal 알고리즘 Kruskal 알고리즘은 탐욕법(Greedy Algorithm, 이하 그리디)이라는 기법을 사용한다. 그리디 알고리즘은 어떤 결정을 해야 할 때마다 "그 순간에 최적"이라고 판단되는 것을 선택하는 방법이다. 물론 순간 최적의 선택이 궁극적으로 최적의 결과를 이끌어 낸다는 보장은 없다. 따라서 그리디 알고리즘은 항상 최적의 해답을 주는지 검증해야 한다. 하지만, Kruskal 알고리즘은 최적의 결과를 보장한다는 것이 증명되었다. Kruskal 알고리즘은 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 위 과정을 반복해 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구한다. Kruskal() (1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다. (..

10-3. 최소 비용 신장 트리란?

신장 트리란? 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리이다. 신장 트리도 트리의 일종이므로 모든 정점들이 연결되어 있고, 사이클이 없어야 한다. 신장 트리는 그래프의 n개의 정점을 (n - 1)개의 간선으로 연결한다. 신장 트리를 찾기 위해 DFS, BFS를 이용할 수 있고, 하나의 그래프에는 많은 신장 트리가 존재한다. 최소 비용 신장 트리란? 최소 비용 신장 트리(MST, minimum spanning tree)는 가중치 그래프의 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 트리이다. 즉, 어떤 그래프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 가장 작은 신장 트리이다. MST는 실생활의 다양한 곳에서 활용된다. 도로 건선 : 도시들을 모두 연결하..

10-2. [C/C++] 인접 행렬을 이용한 가중치 그래프의 구현

인접 행렬을 이용한 가중치 그래프의 구현 이전에 구현했던 AdjMatGraph 클래스를 상속해 가중치 그래프 클래스 WeightGraph 클래스를 구현해보자. 9-2. [C/C++] 인접 행렬을 이용한 그래프의 구현 컴퓨터에서 그래프를 표현하는 방법에는 배열을 사용하는 인접 행렬(adjacency matrix)과 연결 리스트를 사용하는 인접 리스트(adjacency list)의 두 가지가 있다. 인접 행렬을 이용한 그래프의 표현 정 seongmoahn.tistory.com 이전 글에서도 얘기했듯이 INF는 두 정점이 연결되어 있지 않은 상태임을 나타낸다. 무방향 가중치 그래프를 구현했으므로 간선을 추가할 때는 양방향으로 연결해준다. // WeightGraph.h #include "AdjMatGraph.h..

10-1. 가중치 그래프란?

가중치 그래프(weighted graph)란? 가중치 그래프는 간선에 비용이나 가중치가 할당된 그래프이다. 가중치 그래프는 정점의 연결 정보뿐만 아니라 연결에 필요한 비용(거리, 시간, 비용 등)을 함께 표현할 수 있다. 가중치 그래프의 응용 분야는 매우 다양하다. 위 그림과 같은 지도, 인터넷 망과 같은 컴퓨터 네트워크 등 실생활에 밀접한 그래프를 표현하기에 적합하다. 가중치 그래프의 표현 가중치가 없는 그래프에서는 그래프 정보를 저장할 때 정점들 간의 연결 관계만들 저장했다. 연결이 되어 있다면 1, 아니라면 0 이런 식이었다. 하지만, 가중치 그래프에서는 단순 연결 관계만을 저장하는 것이 아니다. 간선의 가중치 값이 0이나 1 일수도 있기 때문에 연결 되어 있지 않은 상태를 0으로 저장하면 안된다...