본문 바로가기

Probelm Solving/Algorithm8

Lazy Propagation Lazy Propagation 배열의 구간 쿼리, 구간 합을 빈번하게 수행할 때 비교적 적은 횟수로 쿼리를 수행하는 방법 Segment Tree, Fenwick Tree 활용의 연장선에 있다. 배열 X에서 구간 쿼리를 수행하고 구간 합을 구할 때 한 개의 트리만 사용할 경우 구간의 길이만큼 쿼리를 수행해야 한다. 이때 추가적인 트리를 사용하면 쿼리를 적은 횟수 수행하고 두 트리를 모두 사용해 구간 합을 구할 수 있다. 0으로 초기화된 배열 X에서 다음 구간 쿼리를 수행한다고 하자. [4,9]에서 +6 [3,6]에서 -2 두 세그먼트 트리/펜윅 트리 a, b를 아래와 같이 이용할 수 있게 update하자. 구간 [1,4]의 합을 구하는 경우, [1,4] 내에서 6은 X[4]에, -2는 각각 X[3], X[.. 2021. 8. 13.
ETT 오일러 경로 테크닉, 근데 이제 펜윅을 곁들인 Euler Tour Technique 오일러 경로 테크닉 트리의 한 간선을 양방향 간선(or 반대 방향의 간선 두 개)로 생각한 뒤 루트에서 출발해 루트로 도착하는 그래프(트리)의 오일러 사이클을 찾는 것으로 트리를 표현하는 방식이다. * 오일러 사이클은 시작점=종점인 한붓그리기로 이해하면 됨 이렇게 144125566788997233 255667889972144133 255799887662331441 등... 트리가 주어지고 다음과 같은 쿼리가 주어진다고 하자. 1. i번 노드의 모든 하위 노드(자식, 자식의 자식...)의 값을 w만큼 증가한다. or i번 노드의 모든 상위 노드(부모, 부모의 부모...)의 값을 w만큼 증가한다. 2. i번 노드의 값을 출력한다. DFS로도 가능이야 하지만 트리의 깊이가.. 2021. 8. 5.
Euler phi function 오일러 피 함수 Euler phi function 오일러 피 함수 $\varphi \left ( n \right )$ = $n$ 이하 자연수 중 $n$ 과 서로소인 수의 개수 소수 $p$와 자연수 $a$에 대하여 다음을 만족한다. $\varphi \left ( p \right )=p-1$ $\varphi \left ( p^a \right )=p^a-p^{a-1}={p^a} \left ( 1-\frac{1}{p} \right ) $ 또한 $\left ( m,n \right )=1$ 인 두 자연수 $m$, $n$에 대하여 $\varphi \left ( mn \right )=\varphi \left ( m \right ) \varphi \left ( n \right ) $ 따라서 소수 $p$, $q$와 자연수 $a$, $b$.. 2021. 4. 16.
Segment Tree Segment Tree 세그먼트 트리 구간 별 정보를 저장하는 트리 구조로 업데이트가 빈번히 일어나거나 구간이 주어지는 쿼리문을 해결하기 좋다. 가장 유명한 예시로 구간 합이나 구간 내 최대/최솟값을 찾는 문제가 있다. 쿼리에 따라 정보를 저장하면 된다. 배열의 원소는 트리 상 리프(leaf)에 존재하며, Root를 기준으로 왼쪽과 오른쪽에 동일(하거나 한 개 차이)한 개수의 리프 정보에 대해 저장한다. N=8처럼 N=$2^n$꼴이라면 모든 노드에 대해 정확히 절반의 리프 정보를 왼쪽/오른쪽 자식 노드에 저장해 포화이진트리를 만들 수 있다. N=6, 7인 경우 아래와 같이 트리를 만든다. 아래 특징을 기억하면 된다. $n$번 노드의 왼쪽 자식 노드는 $2n$번, 오른쪽 자식 노드는 $2n+1$번이다. $.. 2021. 4. 15.
SCC SCC : 강한 연결 요소 strongly connected components 그래프 내 vertex 중 서로 간의 경로가 양방향 모두 존재하는 vertex들의 집합 X⊂G s.t. ∀a, b∈X, ∃ paths both a→b, b→a DFS와 스택이 핵심이다. 방문 지점의 order(몇 번째로 방문했는지)를 이용한다. DFS함수의 리턴 값은 현재 노드에서 도달할 수 있는 지점 중 가장 먼저 방문한 지점의 방문 순서이다. DFS(cur) = par = cur에서 도달할 수 있는 지점의 ord 중 최솟값 ord[v] v 방문 순서 fin[v] v 방문 완료 여부 = v가 속하는 SCC를 찾았는지? 현재 방문한 지점을 cur, 다음에 방문할 지점을 nxt라 하자. nxt는 다음 세 가지 경우 중 하나에 .. 2021. 4. 13.
Convex Hull과 CCW * Convex Hull: 볼록 껍질 * CCW: counter clockwise, 시계 반대 방향 외적을 이용하는 기하학 문제에서 쓰인다. 주어진 점을 모두 포함하는 볼록 다각형의 꼭짓점을 찾아야 한다. 1. 볼록 껍질의 한 꼭짓점을 찾는다. y좌표가 가장 크거나 가장 작은 점, x좌표가 가장 크거나 가장 작은 점 중 아무거나 고르면 된다. 해당 점을 모두 포함하는 MBR(Minimal Bounding Rectangle)과 볼록 껍질이 무조건 접해야하기 때문 이때는 간단한 비교 함수를 사용해 점을 정렬하고 첫 번째 원소를 기준점으로 잡는다. 2. 기준점을 기준으로 다른 점을 시계방향으로 정렬한다. 이때 외적이 쓰인다. 벡터 OA와 OB의 외적 < 0 ⇒ O를 기준으로 A, B가 시계방향으로 존재한다. .. 2021. 4. 9.
KMP KMP Algorithm Knuth-Morris-Pratt Algorithm 문자열 S와 T가 주어질 때 S가 T를 포함하는지 판단하는 문자열 검색 알고리즘 1. 문자열 T에 대한 pi 배열(size=M)을 구한다. pi배열은 문자열 T 내의 반복된 문자열을 찾아 탐색 시간을 줄이는 데에 쓰인다. pi[ i ] = k ⇔ T[ 0 ~ k ] = T[ i-k ~ k ] ⇔ T의 부분문자열(0~i)의 앞/뒤에서부터 길이 k인 부분문자열이 서로 같다. // Get pi int M = T.size(); vector pi(M, 0); for (int i = 1, j = 0; i 0 && T[i] != T[j]) j = pi[j - 1]; if (T[i] == T[j]) p.. 2021. 4. 9.
행렬의 제곱 분할 정복, DP 문제에서 N이 아주 크게 주어지는 경우 자주 이용됨 분할 정복을 이용한 거듭제곱에 있는 문제 거의 다 이런 문제일 것 같다. struct로 행렬을 구현해 곱셈 연산자 오버로딩. 15행에 출력 조건과 수의 범위에 따라 MOD연산 등을 추가한다. 당연하지만 이때 음수 MOD연산도 주의하자,, 통수 맞을 수 있음,, struct Matrix { int size; vector a; Matrix() { size = 0; } Matrix(int n) { size = n; a = vector(n, vector(n)); } Matrix operator *(const Matrix& X) { Matrix RES(size); for (int i = 0; i < size; i++) { for (int j =.. 2021. 1. 16.

티스토리툴바