cloge 이야기

Dijkstra 다익스트라 알고리즘은 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다.여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말한다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있다. 일단, 다익스트라를 설명하기에 앞서 다익스트라는 그래프 내에 음의 가중치 합을 가지는 사이클이 없을 때에만 동작하고, 음의 가중치를 갖는 간선이 없을 경우에만 언급하는 시간복잡도에 동작함을 언급하고 가겠다. 다익스트라는 아래와 같이 동작한다. (가중치를 거리로 표현하겠다.) 처음, 시작점을 제외한 ..

Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다.서로 다른 원소들이 같은 집합에 속해있는지 판별하는데 쓰인다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. Disjoint Set 사이에는 교집합이 없기 때문에(정의로 인해), 서로간을 합해주는 연산으로 집합이 합쳐지는 과정이 있을 수 있다. 합하는 과정을 매우 빠르게, 그리고 원소를 판별하는 과정또한 매우 빠르게 하기 위해서 DSU를 사용한다. 먼저, Disjoint Set는 트리를 이용하여 표현하는데, 같은 집합에 속한 원소들 중 하나를 루트로 하고, 나머지 원소들을 각각 루트 원소의 자식이 되도록 표현하는 것이다...

Sparse Table이란 전체 N개의 원소들 중 임의의 원소 A에 대해, A를 바로 앞서서 있는 원소가 1개 이하 존재하는 상황에서, 원소 A의 K번째 앞에 있는 원소를 찾는 경우 사용하는 방법이다. (단, 임의의 원소 A를 바로 앞서서 있는 원소는 여럿일 수 있다. 즉, 원소 A의 바로 뒤에 있는 원소의 제한은 없다.) '임의의 원소 A의 K번째 앞에 있는 원소를 찾아라' 라는 질문이 Q번 들어올 경우, 이를 해결하기 위해 Sparse Table이란 방법을 이용하여 빠르게 구할 수 있다. Sparse Table을 이용하지 않고 가장 단순한 방법으로는 O(QN)의 시간복잡도를 가지는 방법이 있다. Naive - O(QN) A의 바로 앞 원소를 알고 있으므로, 쿼리마다 주어진 A에서 바로 앞으로 K번 이..