글

51개

페이지당5 10 20

Floyd-Warshall (플로이드-워샬 알고리즘)

플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다. 하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는…

벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고…

다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다. 만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을…

서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는…

Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며,…