PS 이야기

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 common prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z$ 배열을 문자열 $s$의 Z-function이라고 부른다. 예를 들어, 문자열 "aaaaa"의 경우, $z = [0, 4, 3, 2, 1]$이 되며, 문자열 "aaabaab"의 경우, $z = [0, 2, 1, 0, 2, 1, 0]$이 되고, 문자열 "abacaba"의 경우, $z = [0, 0, 1, 0, 3, 0, 1]$이 된다. Z-function을 $O(n^2)$ 시간복잡도로 naive 하게 구하면 아래와 같이 코딩할 수 있다. vector z_functio..

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다. 실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다. 직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다. 더보기 #include using namespace std; #define MAXN 100005 typedef __int64_t lld; typedef __int128_t lll; i..

참고자료: 위키백과 Stern-Brocot 트리는 모든 양의 유리수가 정점과 일대일이 되는 무한한 완전 이진트리다. 또한, 이진탐색트리처럼 왼쪽에서 오른쪽 방향으로 탐색 가능하다. 연분수에 의한 트리 양의 유리수는 $q$ 는 아래와 같은 연분수 꼴로 표현할 수 있고, 이를 수열 $a$로도 표현할 수 있다. $q = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_k}}}} = [a_0; a_1, a_2, \dots, a_k]$ 여기서 $k$와 $a_0$는 음이 아닌 정수고, 나머지 $a_i$는 양의 정수다. 이러한 표현은 유일하지 않은데 다음과 같이 수열의 맨 끝 $a_k$가 $1$일 때는 중복이 있기 때문이다. $[a_0; a_..

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 잡는다. 2. 정점 $x$에서 가장 먼 정점 $y$를 찾는다. 3. 정점 $y$에서 가장 먼 정점 $z$를 찾는다. 트리의 지름은 정점 $y$와 정점 $z$를 연결하는 경로다. 증명) 트리에서 정점 $u$와 정점 $v$를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 $x$를 정하고, 정점 $x$에서 가장 먼 정점 $y$를 찾았을 때, 아래와 같이 경우를 나눌 수 있다. i. $x$가 $u$ 혹은 $v$인 경우 ii. $y$가 $u$ 혹은 $v$인 경우 iii. $x$, $y$, $u$, $v$가 서..

Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다. $S_i = \sum_{k=1}^{i} x_k$ 를 정의하자. 단, $S_0 = 0$ DP 배열을 아래와 같이 정의한다. $D_i$ = 1번부터 $i$번 병사까지 특공대를 나눌 때 전투력 합의 최대값. 단, $D_0 = 0$ 이 때, 점화식은 아래와 같이 된다. $D_i = \max(D[j] + A(S_i-S_j)^2 ..

2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 구할 수 있다. Claim 1) 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리 중 최대값이 가장 먼 두 점의 거리다. 증명) $N$개의 점들 중 가장 먼 두 점을 $a$와 $b$라 하자. $a$와 $b$를 잇는 선분을 그리고 수직한 직선을 그렸을 때 아래와 같이 된다. 파란색 직선 위를 포함하여 파란색 영역에 $a$와 $b$ 이외에 다른 점들은 존재하지 않다. 만약 존재한다고 가정하면 $a$와 $b$가 가장 먼 두 점이라는 가정에 모순된다. 따라서 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양..

처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $O(N \lg N)$ 시간복잡도를 갖는다. 이를 $O(N)$에 해결할 수 있는 방법을 설명하겠다. 힙의 모양을 구성한 뒤에 맨 아래 정점부터 처리하는데, 부모 정점의 값보다 자신의 값이 우선순위가 더 높다면 부모 정점의 값과 자신의 값을 바꾼다. 이 뒤에 자신의 값의 우선순위가 자기 자식 정점의 값보다 낮을 수 있으므로 마찬가지로 재귀적으로 확인해준다. 이렇게 진행될 경우 아래에서 $h$ 높이에 있는 정점을 처리할 때, 최대 $h$번의 swap이 일어날 수 있다. 이를 수식으로 써서 나타내면 연산회수의 상한은 $n \times \sum{\frac{h}{2^{h-1}}}$ ..

1) Knuth-Morris-Pratt Algorithm 2) Aho-Corasick Algorithm 1) Knuth-Morris-Pratt Algorithm KMP Algorithm은 패턴 $P$와 문자열 $S$가 있을 때, 문자열 $S$에 패턴 $P$가 부분문자열로 있는지, 혹은 몇 개 있는지 선형시간 $O(|S| + |P|)$에 확인하는 방법이다. 기본적인 아이디어는 실패 함수 f(i)에서 온다. 아래는 패턴 $P$가 "abracadabra" 일 때 실패 함수 값을 표로 나타낸 것이다. i 1 2 3 4 5 6 7 8 9 10 11 P a b r a c a d a b r a f 0 0 0 1 0 1 0 1 2 3 4 $P[i, j]$를 패턴 $P$의 $i$번째 문자부터 $j$번째 문자까지로 구성된..

Persistent Segment Tree는 가상으로 $N$개의 Segment Tree를 두는데 공간복잡도는 $O(N \lg N)$인 Segment Tree 구축 기법이다. Persistent Segment Tree는 주로 update 질의가 없는 2D range query에서 쓰인다. 예를 들어, 2차원 좌표상에 $N$개의 점이 있고, x, y 좌표가 모두 1이상 $N$이하이면서, x 좌표가 $N$개의 점에 대해 서로 다르다고 하자. 이 때, 특정 영역에 대해 영역 안의 점의 수를 세는 질의를 $O(\lg N)$ 시간안에 해결할 수 있다. 다음과 같이 $N$개의 Segment Tree와 그 트리에서 함수 count(y1, y2)를 정의하자. 1) Tree[i] = x 좌표가 1이상 i이하인 점들만 있다..

Divide & Conquer Optimization은 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 주로 Dynamic Programming에서 쓰인다고 생각할 수 있으나, Dynamic Programming이 아닌 상황에서도 널리 쓰일 수 있다. 조건 1) DP 점화식 꼴 $D[t][i] = \min_{k < i}(D[t-1][k] + C[k][i])$와 같이 $D[t][i]$ 안에 $D[t-1][k]$와 $k$에 대한 함수 $f(k)$가 들어가 있는 경우 조건 2) $A[t][i]$는 $D[t][i]$를 만족시키는 최소 $k$라 할 때 아래 부등식을 만족 $A[t][i] \leq A[t][i+1]$ 위 두 조건을 만족하면 원래 $O(KN^2)$의 시간복잡도를 갖는 DP를 Divide & ..