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 ..
문제 링크 C. Ceiling Function $K$개의 노드로 구성된 Binary Search Tree가 $N$개 주어진다. 이 때 서로 다른 모양을 갖는 BST의 개수를 구하는 문제다. 구조체를 써서 BST를 구현하고 두 노드에 대해 각 노드를 루트로한 서브트리가 같은지 비교해주는 재귀 함수를 구현하여 쉽게 해결할 수 있다. #include using namespace std; int N, M; int A[21]; struct NODE { NODE(int val=0): val(val) { left = right = 0; } int val; NODE *left, *right; } *root[51]; bool identical(NODE *a, NODE *b) { if ((bool)a->left != (b..
- Total
- Today
- Yesterday
- IOI2011
- IOI2014
- Segment tree
- BOI 2009
- moore
- HackerRank
- ioi
- majority
- IOI2013
- BOI 2001
- Knuth Optimization
- Dijkstra
- Dynamic Pramming
- TRIE
- BOI
- optimization
- vote
- Boyer-Moore Majority Vote Algorithm
- idea
- Greedy Method
- USACO
- Algorithm
- IOI2012
- dynamic programming
- Divide & Conquer
- Splay Tree
- Tree
- z-trening
- Boyer
- Parametric Search
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 |