-
JooDdae's profile image
JooDdae
March 12, 2023
Disjoint Sparse Table
Disjoint Sparse Table은 효율적인 쿼리 처리를 위한 자료구조 중 하나로, 1차원 배열의 range query를 해결하는 데 사용됩니다. 이 자료구조는 $O(N log N)$으로 전처리되며 $O(1)$의 시간복잡도로 range query를 구할 수 있습니다. 일반적인 Sparse Table로 range query를 처리할 때와 같은 시간복잡도를 가지지만, Sparse Table의 경우 쿼리로 찾은 두 구간의 값을 합칠 때 겹치는 부분이 존재하기 때문에 $x \circ x = x$를 만족하는 연산(ex: $max$, $min$, $gcd$)만 가능하지, Disjoint Sparse Table은 그렇지 않은 연산(ex: $+$, $\times$)도 지원합니다. Sparse...
-
JooDdae's profile image
JooDdae
January 16, 2023
조건을 만족하는 최솟값 혹은 최댓값 구하기
문자열이 주어졌을 때, 재배열하여 원본보다 사전 순으로 느린 문자열 중 사전 순으로 가장 빠른 문자열을 찾는 간단한 문제를 하나 생각해봅시다. 가능한 모든 재배열 방법을 확인하는 건 $N!$에 비례하는 시간이 걸리기 때문에 다른 방법을 찾아보아야 합니다. 이 문제를 해결하기 이 글에서 소개하고자 하는 풀이 방법을 이용해 소개하고자 합니다. 확정되지 않은 가장 앞자리에 a를 넣어본 뒤에 가능한지 확인한 후, 가능하다면 확정 지어주고 불가능하다면 다음 문자인 b로 넘어가고, 이를 확정 짓기까지 계속 반복하는 것입니다. 예를 들어 문제의 입력으로...
-
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개)인 리프 노드가 존재하기 때문에...