Algorithm (142) 썸네일형 리스트형 118. Shortest Path Faster Algorithm Shortest Path Faster Algorithm(SPFA)은 벨만-포드 알고리즘을 약간 변형한 것으로 간선을 확인할 때 $d_v$의 값이 변하지 않았을 경우 그 정점과 인접한 정점을 다음 차례에 바로 확인할 필요가 없다는 성질을 이용한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 큐에 정점 $k$를 추가한다. 5. 큐에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$에서 .. 117. Floyd-Warshall 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 그래프의 정점의 수가 $n$일 때 시간복잡도는 $\Theta(n^3)$이다. 플로이드-와샬 알고리즘은 정점들 사이의 최단 거리를 구할 때 중간에 거칠 수 있는 정점의 수를 늘려 나가면서 최단 거리를 갱신하는 방식으로 작동한다. 벨만-포드 알고리즘이 간선을 확인하는 것과는 약간 다르다. 구체적인 작동 방식은 다음과 같다. 1. 정점 $i$로부터 정점 $j$까지의 최단 거리를 $d_{i, j}$라고 한다. 2. 각각의 $d_{i, j}$에 대해 $i = j$인 경우 $d_{i, j} = 0$, $i \ne j$인 경우 $d_{i, j} = \infty$로 초기화한.. 116. Bellman-Ford 벨만-포드 알고리즘(Bellman-Ford Algorithm)은 한 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 그래프의 정점의 수가 $n$, 간선의 수가 $m$일 때 시간복잡도가 $\Theta(nm)$으로 다익스트라 알고리즘에 비해 느리지만, 가중치가 음수인 간선이 존재할 경우에도 최단 경로를 찾을 수 있다. 가중치가 음수인 간선이 존재하는 그래프를 다루기 때문에, 무향 그래프는 사실상 등장하지 않으며 무향 그래프에서의 최단 경로를 다루게 된다. 벨만-포드 알고리즘은 다음과 같은 방식으로 작동한다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할.. 115. Dijkstra 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 정점과 정점 사이의 최단 경로를 찾을 때 가장 많이 사용되는 알고리즘으로, 유향 그래프와 무향 그래프에서 모두 사용할 수 있으나 가중치가 음수인 간선이 없는 그래프에서만 정상적인 작동을 보장할 수 있다. 다익스트라 알고리즘은 기본적으로 시작 정점이 하나로 고정되어 있으며 작동 원리는 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 아직 선택하지 않은 정점들.. 114. Shortest Path 최단 경로(Shortest Path)는 그래프에서 정점과 정점 사이의 경로 중 길이가 가장 짧은 것을 의미하며 그래프 이론에서 기본적인 내용으로 많이 다루어지는 주제이다. 일반적으로 최단 경로를 찾는 대상은 그래프의 정점으로, 트리에서의 최단 경로는 복잡한 요소가 없기 때문에 최단 경로라는 주제로 따로 분리하지 않는다. 아래의 내용이 끝이다. 가중치가 음수인 간선이 하나라도 있다면 그 간선을 무한히 왕복하는 것이 가능하므로 모든 최단 경로의 길이가 $-\infty$가 되며, 가중치가 음수인 간선이 없다면 두 정점 사이의 단순 경로가 두 정점 사이의 최단 경로와 같다. 그래프는 두 정점 사이에 여러 경로가 존재할 수 있으므로 최단 경로를 구하는 것이 더 흥미로운 주제가 된다. 그래프에서 최단 경로를 구하는.. 113. Diameter of Tree 트리의 지름은 다음과 같이 정의된다. 트리에 존재하는 임의의 정점 $u$와 $v$에 대해, 두 정점 사이에는 항상 한 개의 단순 경로가 존재하며 이 단순 경로의 길이를 정점 $u$와 $v$ 사이의 거리(Distance)라고 한다. 트리의 한 정점 $u$과 임의의 정점 $v$에 대해, 정점 $u$와 $v$ 사이의 거리의 최대값을 정점 $u$에서의 이심률(Eccentricity)이라고 한다. 트리의 각 정점에서의 이심률의 최소값을 트리의 반지름(Radius of Tree)이라고 하고 이심률의 최대값을 트리의 지름(Diameter of Tree)이라고 한다. 쉽게 말해서 트리의 지름은 트리에 존재하는 두 정점 사이의 거리의 최대값과 같다. 다음과 같은 트리에서 지름은 $4$, 반지름은 $2$이다. 간선에 가중.. 112. Bipartite Graph 음이 아닌 정수 $k$에 대해 그래프가 다음 조건을 만족하면 그 그래프를 $k$분 그래프(${\color{#FF0000}k}$-partite Graph)라고 한다. 정점을 $k$개의 그룹으로 분리했을 때 간선으로 직접 연결된 두 정점이 항상 서로 다른 그룹에 속하게 할 수 있다. 이중 $k = 2$일 때 조건을 만족하는 그래프를 이분 그래프(Bipartite Graph)라고 한다. 이분 그래프에 존재하는 모든 사이클은 길이(사이클에 포함된 정점의 수)가 짝수이며, 그 역도 성립한다. 모든 트리는 이분 그래프이다. 어떤 그래프가 이분 그래프인지 확인하는 방법은 간단한데, 임의의 정점에서 DFS를 시작해서 인접한 정점을 탐색할 때마다 그 정점을 이전 정점과 다른 그룹에 추가한 다음 DFS가 끝났을 때 간선이.. 111. Grid & Flood Fill 그리드(격자, Grid)는 특수한 형태의 그래프로, $n$차원 좌표공간에 존재하는 점으로 표현되는 정점들과 정점들 사이를 잇는 간선으로 이루어져 있다. $n$은 대체로 $2$이며 가끔씩 $n$이 다른 값인 문제도 존재한다. 또한 점 대신 칸으로 이루어진 그리드가 등장하는 경우도 많은데, 각 칸을 그 중심점으로 바꾸면 정점과 간선으로 이루어진 그리드로 쉽게 변환이 가능하므로 이것은 별로 문제가 되지 않는다. 그리드의 좌표를 인덱스(Index)라고 하는 경우도 많다. 그리드에서 정점 사이를 잇는 간선은 보통 서로 인접한 칸들 사이에는 모두 존재한다. 일반적으로 그리드에서 두 칸이 인접하다는 것은 이렇게 이해할 수 있다: 정점 $\text{A}$의 좌표가 $(a_1, a_2, \ldots, a_n)$이고 정점.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 18 다음
