-
JooDdae's profile image
JooDdae
August 19, 2022
O(N) Precomputation, O(1) RMQ (Farach-Colton and Bender Algorithm)
이 글은 Sparse Table을 이용한 $O(N \log N)$ 전처리, $O(1)$ LCA 쿼리(소멤 글 링크)와 sqrt decomposition를 이용한 $O(N)$ 전처리, $O(\sqrt N)$ RMQ(cp-algorithms 링크)를 선행 지식으로 가지고 있다면 더 쉽게 이해할 수 있습니다. $O(N)$ 전처리, $O(1)$ LCA 쿼리 우리는 LCA 쿼리를 Euler Tour 테크닉을 통해 RMQ로 변환시킬 수 있습니다. 이는 위 Sparse Table을 이용한 $O(1)$ LCA 쿼리에서도 사용하는 방법이기 때문에 위 링크된 소멤 글에 자세히 설명되어 있으므로 이 글에서는 설명을 생략하겠습니다. 이 테크닉을 이용해 주어진 트리에서...
-
JooDdae's profile image
JooDdae
May 18, 2021
Small To Large Merging
Small To Large Merging “작은거를 큰거에 합친다”, 이름만 들으면 무엇인지 유추가 잘 되지 않습니다. 하지만 알고리즘을 공부하는 사람이라면 한 번쯤은 간접적으로라도 접한적이 있을 것입니다. 바로 Union Find의 Union by size에서 시간복잡도를 보장하기 위해 쓰이기 때문입니다. 알고리즘에서 소개한대로 작은 집합을 큰 집합에 합친다면 한번의 Find 연산이 $O(\log N)$만큼 걸린다는 것이 증명되어 있습니다. 이 글에서는 Small to Large Merging을 소개하면서 왜 이런 시간복잡도가 보장되는지 알아보고, 응용되는 문제의 풀이를 설명하겠습니다. 간단한 문제를 하나 풀면서 시작하겠습니다. 무작위의 수가 1개씩...
-
JooDdae's profile image
JooDdae
April 14, 2021
오일러 회로와 경로
이 글에서는 연결 무방향 단순 그래프를 다룹니다. 오일러 회로 그래프의 모든 간선을 단 한 번씩 지나서 시작점으로 돌아오는 경로를 오일러 회로라고 합니다. 연결 그래프면서 차수가 홀수인 정점이 없다면 오일러 회로가 존재합니다. 그리고 오일러 회로가 존재한다면 차수가 홀수인 정점이 없습니다. 오일러 회로와 관련된 문제를 풀기 위해서는 이 필요충분조건만 알고 있어도 되지만 아래에 서술할 증명이 간단하기에 한 번쯤 읽고 넘어가는 것을 추천합니다. 그래프에서 사이클이 존재하지 않기 위해선 트리가 되어야 하지만 트리에는 차수가 홀수(1개)인 리프 노드가 존재하기 때문에...