-
알고리즘 문제 접근 과정 11
알고리즘 문제 접근 과정 11 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Two Machines - ICPC 2019 Seoul Nationalwide Internet Competition L번 관찰 주어진 문제를 간단히 본다면, 머신 A와 머신 B에서 각각 작업에 걸리는 시간이 다른 N개의 일을, A와 B에 적절히 할당하여 동시에 일을 진행하고,...
-
알고리즘 문제 접근 과정 10
알고리즘 문제 접근 과정 10 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Musical Notes - USACO December 2009 Contest Silver 2번 문제가 영어로 되어있어서, 동일한 문제 상황의 번역을 첨부하겠습니다. 문제 카이홀에서는 한창 카이스트 합창 동아리 ‘코러스’의 콘서트가 진행되고 있다. 이번 콘서트에는 총 N개의 곡이 1번부터...
-
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 쿼리에서도 사용하는 방법이기 때문에 위 링크된 소멤 글에 자세히 설명되어 있으므로 이 글에서는 설명을 생략하겠습니다. 이 테크닉을 이용해 주어진 트리에서...
-
알고리즘 문제 접근 과정 9
알고리즘 문제 접근 과정 9 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 짐 정리 - KOI 2007 지역본선 중등부 4번 풀이 문제를 간략화하기 위해, 짐들을 옮길 때 드는 힘을 생각하지 않고, 최소 몇 번 만에 짐을 옮겨 정렬할 수 있는지 위 그림을 예시로 확인해봅시다. i)...
-
알고리즘 문제 접근 과정 8
알고리즘 문제 접근 과정 8 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 버스 노선 - KOI 2014 고등부 2번 풀이 이 문제를 해결하는데 큰 어려움이 되는 부분은 구간이 원형으로 되어있다는 점일 것입니다. 그렇다면 일단, 문제가 원형으로 생겨있지 않고 0번을 기준으로 일직선으로 생긴 형태라면 어떻게 해결할...
-
알고리즘 문제 접근 과정 7
알고리즘 문제 접근 과정 7 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 방 청소 - COCI 2013/2014 Contest #5 6번 풀이 문제 상황이 단순하지 않아서, 어떻게 풀지 쉽게 감이 오지 않을 수 있습니다. 한 음료를 담을 수 있는 상자는 두 개뿐이지만, 음료를 어떻게든 옮겨서 담을...
-
알고리즘 문제 접근 과정 6
알고리즘 문제 접근 과정 6 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Exhibition - JOI 2019 2번 주어진 문제가 영문이기 때문에 번역을 하여 문제를 첨부하겠습니다. 문제 알고박물관에서는 새해를 맞이해 여러 작품들을 특별 전시하려 합니다. 이번 특별 전시는 매우 귀한 작품들을 가지고 전시할 것이기 때문에, 전시하는...
-
알고리즘 문제 접근 과정 5
알고리즘 문제 접근 과정 5 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 두 배열의 합 - KOI 2001 고등부 1번 관찰 우리가 생각해볼 수 있는 가장 쉬운 방법은 무엇이 있을까요? 아마 문제에서 나온 방법을 그대로 사용하는 것이 가장 편한 방법일 것입니다. 우리가 만들 수 있는...
-
알고리즘 문제 접근 과정 4
알고리즘 문제 접근 과정 4 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 줄 세우기 - KOI 2013 지역본선 중등부 4번 관찰 최소한의 이동이라는 조건이 없을 때에, 우리는 어떻게 줄을 세울 수 있을까요? 우리는 1번부터 N번까지의 학생을 모두 순서대로 뒤로 보내거나, N번부터 1번까지의 학생을 모두 앞으로...
-
알고리즘 문제 접근 과정 3
알고리즘 문제 접근 과정 3 이번 포스트에서도 ‘알고리즘 문제 접근 방법 1, 2’에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 보석 - Taejon Asia Regional 2001 B번 관찰 금강석의 수를 최대화하기 위해서는, 팔 수 있는 모든 땅을 다 한 번씩 파 몇 개를 얻을 수 있는지 기록한 다음에, 그 중 가장 많이...
-
Persistent Data Structures
Persistent Introduction 과거의 상태를 보존하는 자료구조를 persistent data structure라고 합니다. 예를 들어, persistent array는 과거의 배열의 상태를 담고 있는 “버전”을 갖고 있습니다. 여기에 “버전 $x$에서 $i$번째 원소를 $d$로 바꿔서 버전 $y$를 만들어라”, 또는 “버전 $x$에서 $i$번째 원소의 값을 반환해라” 등의 연산을 적용할 수 있습니다. Persistent segment tree(PST)에 대한 자료는 인터넷에서 많이 찾아볼 수 있습니다. 하지만 persistence라는 개념은 segment tree에만 적용되는 것이 아닙니다. PST는 persistence를 지원하는 일반적인 방법을 segment tree에 적용한 것일 뿐, segment tree만을 위한...
-
알고리즘 문제 접근 과정 2
알고리즘 문제 접근 과정 2 이번 포스트에서도 ‘알고리즘 문제 접근 방법’에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 나무 막대 - Taejon Asia Regional 2001 B번 관찰 우리는 문제를 이해할 때, 복잡하게 주어진 조건을 머리에 표상하기 쉬운 형태로 변경하는 것이 중요합니다. 주어진 조건에서, 한 번 기계를 작동할 때, 그 다음에 오는 막대의...
-
Introduction To Retroactivity
Table Of Contents Introduction Preliminaries Operations Partial Retroactivity Full Retroactivity Runtime General Retroactivity Specific Retroactivity Queue Deque Union-Find Priority-Queue Summary Introduction 안녕하세요, Aeren입니다! Persistent data structure는 어떤 data structure의 여러 상태를 저장하면서 임의의 상태로부터의 연산을 통해 도달한 새로운 상태를 관리할 수 있게 합니다. 이렇게 만들어진 상태들의 관계는 tree 구조룰 이루게 되죠. 이번 글에서 소개할 내용은 이와 대비되는 개념인 retroactive data structure입니다. Retroactive data structure에서 각 상태들의 관계는 line graph형태로 고정되있습니다. 그리고 어떤 상태가 연산을 통해...
-
서로 다른 수와 쿼리
개요 다음 문제를 생각해 봅시다. 수열과 쿼리 5 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 쿼리 $Q$개가 주어집니다. $i$번 쿼리마다 $l_i, r_i$가 주어지면, $[l_i,r_i]$ 구간에 존재하는 서로 다른 수의 개수를 구해야 합니다. ($1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 1 \leq A_i \leq 10^6, 1 \leq l_i \leq r_i \leq N$) 위 문제(이하 서로 다른 수와 쿼리 문제)는 problem solving을 하다 보면 가끔 맞닥뜨리게 되는데, 유명한 문제인 만큼 $O(N\sqrt{Q})$나 $O((N+Q)\log{N})$등의 다양한 풀이...
-
알고리즘 문제 접근 과정
알고리즘 문제 접근 과정 알고리즘 문제 풀이를 진행하면서, 어느정도 순간에서부터는 내가 모르는 알고리즘 및 자료구조가 필요하다는 점에서 문제 풀이의 어려움을 느끼게 됩니다. 더 발전하기 위해서 다양한 내용들을 찾아서 공부하고 이를 구현하는 방법을 익히는 과정이 필요하게 됩니다. 하지만 처음 공부할 때에 실제로 제가 가장 많이 겪었던 문제, 혹은 다른 사람들이 처음 공부를 시작 하면서 어려웠던 점들에 대해 이야기를 들을 때에 공통적으로 나왔던 부분은 바로, 알고리즘과 자료구조를 알고 있어도, 해당 문제를 어떤 알고리즘과 어떤 자료구조를 사용해야 하는지...
-
스킵 리스트
서론 다음 연산을 모두 $O(logn)$에 지원하는 자료구조가 필요합니다. x를 추가한다. x를 삭제한다. x 이상의 원소 중 가장 작은 것을 출력한다. C++에서는 std::set가 바로 이 역할을 하지만, Python에는 이런 내장 라이브러리가 없습니다. 그래서 외부 라이브러리를 쓰지 않는 한 레드-블랙 트리나 AVL 트리 등을 직접 구현해야 하는데, 트리 자료구조는 보통 rebalancing 과정이 복잡합니다. 한편, 트리의 틀을 벗어나면 스킵 리스트 (Skip List)라는 자료구조가 있습니다. “평균”이라는 말에서 추측할 수 있듯이, 랜덤을 사용한다는 특징이 있습니다. AVL 트리 등에 비해 구현이...
-
Data Structure For Range Mode Query
Table Of Contents Introduction Hardness Result First Method Second Method Third Method Final Method Introduction 안녕하세요, Aeren입니다! Competitive programming을 해본 적 있는 분이라면 range sum query, range minimum query 등등의 다양한 range query문제를 접해보셨을 것입니다. 많은 range query problem들은 linear memory만으로 sublinear time query를 가능하게 해주는 data structure가 존재합니다. 이번 글에서는 비슷한 맥락의 range mode query 를 해결하는 linear memory data structure에 대해 알아 볼 것입니다. 이 글은 다음 논문을 바탕으로 작성되었습니다. Array 혹은 multiset...
-
Incremental Topological Ordering and Strong Component Maintenance
Incremental Topological Ordering and Strong Component Maintenance 방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 위상 정렬은 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이다. 그래프는 일반적으로 순서가 없이 표현되는데, 문제를 풀거나 처리를 하는 데 있어서...
-
Stack 자료구조와 실습
Stack Stack이란 스택 자료구조란 항상 한쪽 방향에서만 자료의 입력 및 출력이 가능한 형태의 선형 자료구조입니다. 책상 위에 책을 무더기로 쌓아놓은 상태를 생각하면 스택 구조를 이해하기 쉽습니다. 여러 개의 책이 쌓인 상태에서, 우리는 가장 위에 놓여져 있는 책만 쉽게 들어올릴 수 있으며, 가장 위에만 새롭게 책을 놓는 것이 쉽습니다. 물론 중간에 있는 위치에 책을 넣거나 빼는 것도 가능하지만, 이를 위해서는 그보다 위에 있는 책들을 들어야 하죠. 여기서 가장 위에 있는 책이라는 의미는, 책들이 쌓이기 시작했을 때...
-
Heavy-light Decomposition With Globally Balanced Binary Trees
Table Of Contents Prerequisite Introduction Main Idea Implementation Benchmark Prerequisite Segment tree - Tutorial on cp-algorithms Heavy-light decomposition - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 다음 문제를 생각해봅시다. Monoid $(T,+)$와 $(L,+)$, left monoid action $\ast(\ast):(L,T)\rightarrow T$, tree $G=(V,E)$와 각 node의 가중치 $W:V\rightarrow T$이 주어진다. 다음 연산들을 수행하라. $u,v\in V$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 $\sum_{w\in P}W(w)$의 값을 출력한다. $u,v\in V$와 $f\in L$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 각 $w\in...
-
Li Chao Tree의 Lazy Propagation
개요 리차오 트리는 직선들을 관리하는 동적 세그먼트 트리의 일종으로, Convex Hull Trick 등등에서 쓰이는 자료구조입니다. 다른 세그먼트 트리와 마찬가지로 리차오 트리에도 레이지 프로퍼게이션을 적용할 수 있지만, 이에 대해서는 잘 알려져 있지 않습니다. 이 글에서는 리차오 트리에 레이지 프로퍼게이션을 적용한 확장 연산들과 그 활용에 대해 소개합니다. 리차오 트리 좌표 범위가 $N$일 때, 기본적인 리차오 트리는 다음과 같은 연산들을 할 수 있습니다. insert(a,b) : 새로운 직선 $y=ax+b$를 삽입한다. $O(\log{N})$ get(x) : 주어진 $x$좌표에서 $y$좌표의 최솟값을 구한다. $O(\log{N})$...
-
Shortest Path Algorithm - Dijkstra
Dijkstra 다익스트라 알고리즘은 그래프에서 한 정점(시작 정점)에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘입니다. 여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말합니다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있습니다. 다익스트라는 알고리즘의 구조 상 다음과 같은 성질들을 가지게 됩니다. 그래프 내에 음의 가중치 합을 가지는 사이클이 있을 경우에, 다익스트라를 통한...
-
접미사 트리 (파트 2: Ukkonen의 알고리즘)
이전 글에서 이어집니다. Ukkonen의 $O(m^3)$ 알고리즘 Ukkonen의 알고리즘은 접미사 트리를 $O(m)$에 만드는 알고리즘입니다. 하지만 이를 모두 설명하기에는 너무 복잡하니, 비효율적인 버전을 먼저 서술하고 시간 복잡도를 점차 줄여 나갑시다. (구현할 때도 파트 1을 먼저 구현하고, stress test 등으로 구현이 정확함을 확인하시는 것을 권합니다.) $S[1..i]$의 접미사 트리를 $I_i$라고 표기합시다. Ukkonen의 알고리즘의 큰 그림은 $I_1$에서 시작해서 이것을 $I_2$로 확장하고, $I_3$, $\cdots$, 마지막으로 $I_m$으로 확장하는 것입니다. $m$번째 글자가 끝 문자라고 가정하면 $I_m$의 모든 리프 노드와 접미사가 일대일 대응이 되지만,...
-
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Expander Decomposition and Pruning: Faster, Stronger, and Simpler 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는...
-
Queue Undo Trick
개요 최근에 소개된 아이디어라 한글 자료가 없어서 글을 작성하게 되었습니다. 자료구조의 업데이트 연산이 Amortized 시간복잡도를 갖지 않는다면 가장 최근에 한 업데이트를 취소하는 롤백 연산도 같은 시간복잡도에 구현할 수 있음이 알려져 있습니다. 이 글에서는 롤백 연산의 아이디어를 활용한, 가장 오래된 업데이트를 취소하는 Queue-Undo 연산에 대해 소개합니다. 이 연산은 기존의 Offline Dynamic Connectivity 알고리즘과는 달리 온라인으로 동작한다는 장점을 가지고 있습니다. 유니온-파인드 자료구조에 Queue-Undo 연산을 구현해서 연습 문제들을 해결할 것이기 때문에, 사전 지식으로 유니온 파인드를 알고 있음을 가정하고...
-
Skew-binary Lifting
Table Of Contents Prerequisite Introduction Implementation Performance Analysis Benchmark Prerequisite Binary Lifting - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 이 글에서 소개할 내용은 skew-binary number system을 기반으로 한 skew-binary lifting입니다. 이 글은 An Applicative Random-Access Stack by Eugene W. MYERS을 기반으로 작성되었습니다. 일반적인 binary lifting과의 차이점 중 하나는 각 node $u$가 $O(\log(\textrm{depth}[u]))$ 대신 $O(1)$ 만큼의 공간을 필요로 한다는 것입니다. 표로 정리하면 다음과 같습니다. (Time) / (Additional Space Required) Operation Binary Lifting Skew-binary Lifting Add A...
-
Top Tree로 Dynamic Tree 관리하기
Top Tree로 Dynamic Tree 관리하기 이 글을 읽기 이전에 동적 계획법을 최적화하는 9가지 방법 (4/4) 의 “Dynamic Tree DP” 단원을 이해하는 것이 좋다. 이 글은 해당 내용을 잘 이해하고 있다고 가정하고 설명한다. 그래프의 특수한 경우인 트리는 PS를 포함한 알고리즘 전반에서 자주 활용되는 구조이다. 트리는 일반적인 그래프에 비해 여러 방면으로 효율적으로 관리할 수 있다. 이러한 방법은 그 자체로도 관심의 대상이 되며, 그래프 문제를 풀 때도 다양하게 응용할 수 있다. 너무나도 중요하다는 사실이 잘 알려져 있으니, 구태여...
-
Disjoint Set & Union-find
Disjoint Set Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. 모든 집합들 사이에 공통된 원소가 존재하지 않는다는 것을, 각 원소들은 하나의 집합에만 속함을 의미하므로, 모든 원소들은 자신이 속해있는 유일한 집합만을 가지게 됩니다. Disjoint set data structure를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는데에 유용히 사용할 수 있습니다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. 정의에 의해 Disjoint Set...
-
접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...
-
압축 트라이 (Compressed Trie)
서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열 집합의 prefix를 관리하는 자료구조입니다. 예를 들어 문자열 집합이 {“baby”, “bank”, “be”, “bed”, “box”, “dad”, “dance”}라면 이 집합을 표현한 트라이는 아래 그림과 같습니다. 이 때 붉은색 테두리는 여기서 끝나는 문자열이 존재한다는 것을 의미합니다. 이를 앞으로 valid한 노드라고...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3) Chapter 4: Continued 4.2. Contraction 4.2.1 Properties of Contraction Lemma 4.2를 사용하여 우리는 Non-tree edge의 개수가 작은 Decremental MSF 알고리즘으로 문제를 환원하였다. 이제 이를 Edge의 개수가 작은 Decremental MSF 알고리즘으로 다시 환원한다. 다행이도, 이 부분은 Competitive Programming에서 익숙한 내용이라서 배경 지식이 있다면 빠르게 이해할 수 있다. Definition 4.11. (Connecting Paths). 트리 $T = (V, E)$ 와 터미널의 집합 $S \subseteq V$ 가 있을 때, $P_{S}(T)$ 는...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2) Chapter 3. Continued Proof of Lemma 3.4: The Algorithm. $G_0, \alpha_0, l$ 을 Lemma 3.4의 입력이라고 하자. 알고리즘은 $l + 1$ 개의 레벨 로 그래프를 관리한다. 각 레벨은 간선의 부분집합을 관리하며, one-shot expander pruning algorithm을 호출한다. 레벨이 깊을 수록 (숫자가 클 수록) one-shot expander pruning algorithm의 호출 횟수는 많아지며, 반대로 간선의 개수는 적어진다. 정확히 어떠한 원리인지는 후술하고, 아래 필요한 정의를 나열한다. $\delta = \frac{2}{l}$ 이다. $n,...
-
STL set을 이용한 Convex Hull Trick 구현
소개 Convex Hull Trick은 여러 일차 함수들의 최댓값이나 최솟값을 찾고자 할 때 유용하게 쓰이는 테크닉입니다. 이미 많은 대회에 출제된 바 있어 최근에는 대회를 준비한다면 필수적으로 알아야 할 테크닉이기도 합니다. 혹시 이 기법에 대해 잘 모른다면 구글 등에 검색하셔서 공부하시는 것을 추천드립니다. 잘 설명된 글들이 많기 때문에 여기서는 기법에 대한 자세한 내용까지는 다루지 않을 것입니다. 주어지는 일차 함수들의 기울기가 증가하거나 감소한다면 스택 자료구조 하나만으로 간단하게 Convex Hull Trick을 구현할 수 있습니다. 만약 그렇지 않고 기울기가 들쑥날쑥한다면...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 4)
동적 계획법을 최적화하는 9가지 방법 (Chapter 4) 이 글은 Chapter 3에서 계속된다. 9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자....
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 3)
동적 계획법을 최적화하는 9가지 방법 (Chapter 3) 이 글은 Chapter 2에서 계속된다. 8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = S, m = T$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le S - 1$ 에 대해, $LCS(S[i:]...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 2)
동적 계획법을 최적화하는 9가지 방법 (Chapter 2) 이 글은 Chapter 1에서 계속된다. 4. Knuth’s Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할...
-
C++ STL 컨테이너의 메모리 사용량 (2)
지난 포스트 C++ STL 컨테이너의 메모리 사용량 (1)에서는 list, vector, deque의 내부 메모리 사용량을 분석하고, 어떤 식으로 구현되어있는지 추측해보았습니다. 이번 시간에는 priority_queue, set, map, unordered_map을 다루도록 하겠습니다. priority_queue 컨테이너 priority_queue 컨테이너는 다음과 같은 형태로 정의됩니다. template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; T는 타입, Container는 내부적으로 사용할 컨테이너, Compare는 heap을 구축하는데 사용할 함수를 의미합니다. 기본적으로 priority_queue는 std::vector<T>를 이용하고, std::less를 통해 max heap을 만듭니다. priority_queue는 heapify 등을 통해서...
-
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...
-
2D Segment Tree
안녕하세요, 이번 글에서는 2D Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree에 관한 기초 지식 2D Segment Tree를 이해하기 위해서는 Persistent Segment Tree 포스팅 때와 비슷하게 Segment Tree에 대한 이해가 선행되어야 합니다. Segment Tree가 무엇인지, 혹은 Dynamic Segment Tree가 무엇인지 모르고 있다면 먼저 링크를 타고 그 부분을 공부한 후에 오시는 것을 추천드립니다. Bottom-Up 방식의 Segment Tree Segment Tree를 구현하는 방법으로는 Top-Down 방식과 Bottom-Up 방식이 있습니다. 이전 글에서는 Top-Down 방식만을 설명했으나 2D Segment Tree에서는 Bottom-Up 방식을...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
동적 계획법을 최적화하는 9가지 방법 (Chapter 1) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식...
-
C++ STL 컨테이너의 메모리 사용량 (1)
C++로 Problem Solving을 하는 사람도, 일반적인 프로그래밍을 하는 사람도 C++의 컨테이너는 매우 유용하게 사용합니다. 대표적인 예시가 동적 배열인 vector, 이진 탐색 트리인 set 등입니다. 이러한 자료구조를 적재적소에 사용하지 않으면 시간/공간 복잡도가 예상을 뛰어넘을 수 있습니다. 대표적인 예시가 “priority_queue가 set보다 빠르다”는 말입니다. 이는 일반적으로 사실이지만, 왜 그럴까요? 이와 관련된 질문에 답하기 위해 C++ 컨테이너가 메모리를 원소별로 얼마나 할당하고 그 이유는 무엇일지 gmem이라는 라이브러리를 통해 파트별로 알아보도록 하겠습니다. gmem 라이브러리 gmem은 동적으로 메모리를 할당할 때마다 로그를 남기고,...
-
Wavelet Tree
Wavelet Tree란? Wavelet tree란, 문자열을 저장하는 자료구조입니다. 이진 트리 형태로, 문자열의 길이 $L$에 대해 $L + o(L)$의 메모리를 사용하여(이런 특성이 있는 자료구조를 간결한 자료구조(succinct data structure)라고 합니다) 아래 두 연산을 지원합니다. $\mathbf{rank}_c(x)$: 문자열의 첫 인덱스부터 $x$번째 인덱스까지 문자 $c$가 등장하는 횟수를 반환합니다. $\mathbf{select}_c(x)$: 문자 $c$가 $x$번째로 등장하는 인덱스를 반환합니다. Wavelet이라는 이름은 신호를 재귀적으로 저주파수와 고주파수로 나누어 분해하는 wavelet transform의 이름에서 가져왔습니다. Wavelet tree의 구조 이 문단에서는 일반적인 wavelet tree의 개략적인 구조만을 다룹니다. 구조를 이해하셨다면 다음...
-
Persistent Segment Tree
안녕하세요, 이번 글에서는 Persistent Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. 이미 대다수의 독자분들이 Segment Tree에 대해 알고 있겠지만 다시 한 번 짚고 넘어가겠습니다. Segment Tree는 배열을 여러 구간으로 나누어 관리하는 구조로, $N$개의 원소가 있을 때 구현에 따라 2배에서 4배 정도의 추가 공간이 필요하지만 원소의 변경, 특정 범위 내의 원소의 연산을 $lgN$에 수행할 수 있습니다. 구체적으로 배열 1 2 3 4 3 2...
-
Treap
목차 1. 개요 2. 개념 3. 구현 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이 포스트를 쓰며 언제 한번, Treap의 활용성에 대해서 적고 싶었다. 물론 여기서 내가 여러분에게 소개하고자 하는 것은 Treap을 BST로서 다루는 것이 아닌, 배열을 자유롭게 붙이고 떼고 뒤집는 것에 설명하기 위함이다. Treap은 기본적으로 BST로서 사용할 수 있지만, Splay Tree 처럼 배열을 다루는 데 사용할 수 있다. Splay Tree 처럼 여러가지의 method 들을 활용하여 amortized 시간을 내는것은 아니고, 확률에 의존하는 경향이...
-
Bloom Filter
안녕하세요, 오늘은 Bloom Filter 와 변종들중에 하나인 Scalable Bloom Filter 에 대해서 알아보는 시간을 가지려고 합니다. 너무 자세하거나 수학적인 설명은 배제하고 직관적인 이해를 기반으로 포스팅하겠습니다! 자세한건 그냥 논문을 보세요… » 이 글을 좀 더 좋은 가독성으로 읽기 « Bloom Filter 란? Bloom Filter 는 집합내에 특정 원소가 존재하는지 확인하는데 사용되는 자료구조입니다. 이러한 “membership test” 용도로 사용되는 자료구조들은 Bloom Filter 외에도 다양합니다. 대표적이고 널리 알려진 것으로는 Balanced Binary Search Tree (AVL, red-black tree 등) 과 해시...
-
트리의 종류와 이해
트리의 종류와 이해 0. 목차 목차 tree란? tree의 종류 결론 참고자료 1. tree란? tree 자료구조는 그래프의 한 종류로, 정의 내리자면 트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이 때 각 노드는 재사용 되지 않는 구조이다. tree 에는 여러가지 특징들이 존재한다. tree 의 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다. tree 에는 사이클을 가지는 노드 집합이 존재하지 않는다. tree 반드시 하나의 root가 존재한다. (부모 노드가 존재하지 않는 노드) 이런...
-
O(1) LCA Algorithm (with Sparse Table)
목표 및 문제 소개 LCA(Lowest Common Ancestor)란 루트가 정해진 트리에서, 두 노드 간의 공통 조상이면서 루트에서 가장 먼 노드를 뜻합니다. 노드가 $N$개인 트리에서 임의의 두 노드 간의 LCA를 쿼리당 $O(lgN)$에 구하는 알고리즘은 잘 알려져 있습니다. 각 노드별로 $ 2^k $ 번째 조상을 미리 계산해둔 뒤, Binary Lifting을 활용해 구하는 방식입니다. 이에 대한 지식이 부족하다면 링크 에서 먼저 공부한 뒤에 이 글을 읽으시는 것을 추천합니다. 이 글에서 소개하고자 하는 알고리즘과 밀접한 관련은 없지만, 전반적인 개념에 도움이...
-
효율적인 긴 문자열 연산을 위한 Rope 자료구조
로프와 쿼리 최근 백준 온라인 저지에 로프와 쿼리라는 이름의 베타 문제가 올라왔습니다. 그런데 문제 본문의 어디를 보아도 로프라는 단어는 쓰이지 않고, 줄과 관련되어 보이는 부분도 없습니다. 그저 문자열의 일부를 잘라서 앞이나 뒤로 옮기는 쿼리를 수행하는 문제일 뿐입니다. 그러면 이 문제의 이름은 왜 로프와 쿼리인 걸까요? 일반적인 문자열 자료구조로는? 우선 이 문제를 단순한 std::string 객체로 해결을 시도해 봅시다. #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int q; cin...
-
LiChao Tree (with Dynamic Segment Tree)
목표 LiChao Tree는 직선이 실시간으로 추가되는 Convex hull trick 문제를 해결하기 위한 자료구조입니다. 구현이 비교적 간단하면서 유용한 자료구조인데, 한글로 설명된 자료가 없어 포스트를 작성하게 되었습니다. 이 포스트의 목표는 LiChao Tree를 이용해 (백준 12795) 반평면 땅따먹기 문제를 해결하는 것입니다. 이 문제를 해결하는 방법은 다양하지만, LiChao Tree를 사용한 솔루션이 가장 수행시간이 빠릅니다. 사전지식 - Dynamic Segment Tree LiChao Tree는 Dynamic Segment Tree에 기반한 자료구조입니다. Dynamic Segment Tree란 구간의 범위에 따라 모든 노드를 만들어놓고 시작하는 일반적인 Segment Tree와는...