PS 이야기

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 & ..

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 \leq d$ 조건 3) Monotonicity (단조성) $C[b][c] \leq C[a][d], a \leq b \leq c \leq d$ 조건 2와 조건 3을 만족하면 $A[i][j]$ = $D[i][j]$가 최소가 되기 위한 가장 작은 $k$라고 했을 때 아래 식을..

Majority Vote Algorithm은 사람들이 투표를 했을 때 과반의 표를 받은 대상이 있는지, 그 대상은 누구인지 최소 회수의 비교를 통해 밝혀내는 방법이다.비교라는 것은 check(i, j) 라는 함수 호출을 통해 i번 사람과 j번 사람이 같은 대상에게 표를 던졌는지 확인하는 작업이다. 최소 회수의 비교라는 것은 check(i, j) 루틴을 최소의 회수로 부른다는 것을 의미한다. 두 가지 알고리즘을 소개할 것이다. 두 알고리즘 모두 check(i, j)를 최대 $\lfloor\frac{3}{2}N\rfloor$번 호출한다. Algorithm 1) Boyer-Moore majority vote algorithm 1번 사람부터 $N$번 사람까지 투표한 상황이 아래와 같다고 하자.3 1 2 2 1 ..

Grundy Number는 게임 문제에서 많이 사용되는 방법 중 하나다. Grundy Number는 게임 상황을 Nim Game으로 변환 시켜주는 과정이라고 볼 수 있다. 어떤 상황 $S$에 대한 Grundy Number를 구하는 방법은 아래와 같다. 상황 $S$에서 다음 상황들 중 하나를 $S'$라고 하자. $G(S) = \min(v) $ ($v \not\in \{G(S')\}$) 즉, 상황 $S$의 Grundy Number $G(S)$는 상황 $S$의 다음 상황들 $S'$의 Grundy Number $G(S')$들 중 존재하지 않는 가장 작은 수다. 각 상황들을 Grundy Number로 표현했을 때, 필승법의 여부는 Nim Game과 마찬가지로 구하면 된다. Grundy Number로 표현된 각 상..

Suffix Array (접미사 배열) Suffix Array(韓: 접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 문자열 관련된 문제에서 자주 쓰이는 방법이다. 예를 들어, 문자열 $S = banana$가 있다고 하자. 문자열 $S$의 접미사들은 아래와 같다. suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 문자열 $S$의 접미사 배열은 아래와 같다. suffixia6ana4anana2banana1na5nana3 접미사 배열에서 문자열을 배열로 가지고 있으면 공간복잡도가 $O(N^2)$이기 때문에 접미사를 나타내는 정수 $i$를 가지고 있는다. 즉, "banana"의 접미사 배열은 [6,4,2,1,5,3] 이다. 접미사 배..

Manacher's Algorithm은 문자열 내에서 회문(팰린드롬, palindrome)을 찾는 것과 관련된 알고리즘이며, 시간복잡도는 $O(N)$이다. (여기서 $N$은 문자열의 길이) 이 알고리즘은 문자열 $S$에 대해 아래와 같은 배열을 구할 수 있다.문자열 $S$의 길이, $|S| = N$과 같은 길이의 정수 배열 $A$$A$의 $i$번째 원소 $A[i]$는 $i$번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기 (회문의 길이가 5이면, 반지름은 2가 됨)즉, 부분 문자열 $S[i-A[i] ~ i+A[i]]$는 회문이며, $S[i-A[i]-1 ~ i+A[i]+1]$은 회문이 아니다. 예를 들어, "banana"라는 문자열 $S$에 대한 배열 $A$는 아래와 같다. $S$ b a n a n ..