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 ..
- Total
- Today
- Yesterday
- majority
- Boyer
- z-trening
- IOI2012
- TRIE
- Knuth Optimization
- IOI2013
- Divide & Conquer
- Boyer-Moore Majority Vote Algorithm
- IOI2014
- Segment tree
- optimization
- Dijkstra
- Dynamic Pramming
- Greedy Method
- BOI
- Splay Tree
- BOI 2009
- vote
- Parametric Search
- BOI 2001
- idea
- dynamic programming
- Tree
- moore
- IOI2011
- Algorithm
- ioi
- USACO
- HackerRank
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |