PS 이야기

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

Convex Hull Optimization이란, Convex Hull Trick이라고도 알려져있으며 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다. IOI2002에 처음 나왔다고는 하나, 제대로 알려지기 시작한 것은 APIO2010 특공대 문제 이후라고 생각한다. 때문에 APIO2010 특공대 문제를 예시로 Convex Hull Optimization 설명을 시작하겠다.$S_i = \sum_{k=1}^{i}{x_k..

2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 해결할 수 있다. Claim 1) 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리 중 최대값이 가장 먼 두 점의 거리다. 증명) $N$개의 점들 중 가장 먼 두 점을 $a$와 $b$라 하자. $a$와 $b$를 잇는 선분을 그리고 ..

처음 배열에서 힙을 구성할 때 선형시간으로 구성하는 방법이 있다. 일반적으로 각각의 원소를 삽입하는 방식으로 힙을 구성하면 자명하게 $O(N \lg N)$ 시간복잡도를 갖는다. 이를 $O(N)$에 해결할 수 있는 방법을 설명하겠다. 힙의 모양을 구성한 뒤에 맨 아래 정점부터 처리하는데, 부모 정점의 값보다 자신의 값이 우선순위가 더 높다면 부모 정점의 값과 자신의 값을 바꾼다. 이 뒤에 자신의 값의 우선순위가 자기 자식 정점의 값보다 낮을 수 있으므..

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$가 "abraca..

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$개의 점에 대해 서로 다르다고 하자. 이..

Divide & Conquer Optimization은 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 주로 Dynamic Programming에서 쓰인다고 생각할 수 있으나, Dynamic Programming이 아닌 상황에서도 널리 쓰일 수 있다. 조건 1) DP 점화식 꼴 $D[t][i] = \min_{k < i}(D[t-1][k] + C[k][i])$ 조건 2) $A[t][i]$는 $D[t][i]$를 만족시키는 최소 $..

Knuth Optimization은 Dynamic Programming에서 점화식이 특정 조건을 만족할 때 활용할 수 있는 최적화 기법이다. 조건 1) DP 점화식 꼴 $D[i][j] = \min_{i < k < j}(D[i][k] + D[k][j]) + C[i][j]$ 조건 2) Quadrangle Inequalty (사각부등식) $C[a][c] + C[b][d] \leq C[a][d] + C[b][c], a \leq b \leq c ..

Majority Vote Algorithm은 사람들이 투표를 했을 때 과반의 표를 받은 대상이 있는지, 그 대상은 누구인지 최소 회수의 비교를 통해 밝혀내는 방법이다.비교라는 것은 check(i, j) 라는 함수 호출을 통해 i번 사람과 j번 사람이 같은 대상에게 표를 던졌는지 확인하는 작업이다. 최소 회수의 비교라는 것은 check(i, j) 루틴을 최소의 회수로 부른다는 것을 의미한다.두 가지 알고리즘을 소개할 것이다. 두 알고리즘 모두..

Grundy Number는 게임 문제에서 많이 사용되는 방법 중 하나다. Grundy Number는 게임 상황을 Nim Game으로 변환 시켜주는 과정이라고 볼 수 있다. 어떤 상황 $S$에 대한 Grundy  Number를 구하는 방법은 아래와 같다. 상황 $S$에서 다음 상황들 중 하나를 $S'$라고 하자. $G(S) = \min(v) $ ($v \not\in \{G(S')\}$) 즉, 상황 $S$의 Grundy Nu..