Circulation

목표Circulation 문제를 Max Flow(혹은 Min Cost Flow) 문제로 환원시킬 수 있음을 이해한다.Circulation이란Definition주어진 flow graph $G(V, E)$에 대하여,$l(a, b)$: $a$에서 $b$로 가는 flow의 lower bound,$u(a, b)$: $a$에서 $b$로 가는 flow의 upper bound,$l(a,b) \le f(a,b) \le g(a,b)$를 만족하고$inflow(x) - outflow(x) = \sum\limits_{(v, x) \in E} f(v, x) - \sum\limits_{(x, v) \in E} f(x, v) = 0$을 만족한다.$src$와 $sink$가 정의되지 않았음에 유의하라.Min cost Circulatio..

2024.12.22

Min Cut과 Max Flow와의 관계

Link to original note: [[Flow Graph]]Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다.  이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다.   세줄 요약: 1) 먼저 임의의 $cut$에 의한 간선 용량의 합($|cut|$)은 $flow$의 합($|flow|$)보다 항상 크기 때문에 모든 $|cut|$은 $max(|flow|)$ 이상이다.2) 임의의 Max Flow를 흘린 다음의 그래프에서, 유량을 조금 더 흘릴 수 있는 Residual graph에서, src로부터 도달할 수 있는 정점들의 집합을 $S$라 할 때, $S$에서 $V \setminus S$까지 가는 모든 간선을 끊는 ..

2024.04.29

Master Theorem

*The content is based on 2022 Fall EE205 MasterMethod Lecture. Master Method is a powerful black box for solving recurrences such as Divide and Conquer Method. Assumption: All subproblems have equal size. $T\left(n\right)$ is the function to analyze operation costs to solve problem size of $n$. Settings 1. Base Case: $\forall$ sufficeiently small $n$, $T\left(n\right) \le$ a constant 2. Recurren..

2022.09.14

Computing Fibonacci Sequence with Matrix Multiplication

Fibonacci Sequence as Recursive Formula $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, \quad ^\forall n \ge 2$ Fibonacci Sequence as Matrix Multiplication Form $\begin{vmatrix} F_n \\ F_{ n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{n-1} \cdot \begin{vmatrix} F_1 \\ F_0 \end{vmatrix}, \quad ^\forall n\ge 1$ Fast Recursive Powering for elements of Monoid Suppose we are calcul..

2022.09.06

Slope Trick - 함수 개형을 이용한 최적화

Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2

2021.05.13

Centroid Decomposition - 센트로이드 분할

센트로이드 분할 1. 존재의의 센트로이드 분할 = 트리에서의 분할 정복 기법 트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때 트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다. 2. 센트로이드란 트리의 무게중심인 정점. 트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다. 이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다. Q) 센트로이드는 항상 존재하는가? A) 그렇다 증명 1) 센트로이드 탐색 알고리즘 임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다. 모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다...

2021.02.28

Persistent Segment Tree 구현 메모

난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..

2021.01.18

Tree DP

www.secmem.org/blog/2019/02/10/TreeDP/ Tree DP 문제 해결 목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 알고리즘 공부를 하면서 오랫동안 다이나믹 프로그래밍을 그것도 트리에서 해결하는 문제를 꽤 안풀었음을 www.secmem.org codeforces.com/blog/entry/20935 DP on Trees Tutorial - Codeforces codeforces.com www.commonlounge.com/discussion/8573ee40c4cb4673824c867715a5bc7b Dynamic Programming on Trees (or Tree DP) | CommonLounge In this tutori..

2020.12.14

BFS 메모리 줄이는 방법

BFS에서 visit 배열을 거리 저장 용도로 사용하고는 한다. int vis[N][M]={}, dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1}; queue q; q.push({sr,sc}); vis[sr][sc] = 1; while(!q.empty()){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; for(int i=0;i0 ; sz--){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; if(r==er && c==ec) return dist; for(int i=0;i0; sz--) 이 for문이 dist 값을 가진 노드들만이 큐에서 빠지게 해준다.

2020.11.18

Li Chao Tree 공부

어떤 기술 X의 사용 범위를 R(X)라 나타내자. R(Convex Hull Tree ) > 1; /* m에서 high가 더 크면 왼쪽에 high 넘기고 오른쪽 업데이트 */ if(cmp(high,low,m)) { tree[nd].v=high; if(tree[nd].r==-1) {..

2020.11.14

Knuth Optimization

DP Optimization Technique 정의 $ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다. $ dp[i][j] = \min_{i

2020.11.12

모든 Mother Vertex를 O(V+E)에 구하는 알고리즘

발행일 : 2020-07-08 UPD1 : 2020-09-25 Find All Mother Vertices in a directed graph. Mother Vertex. 어떤 방향 그래프에서 한 정점이 다른 모든 정점에 도달할 수 있다면 이를 Mother Vertex라 부른다. 이 글에서는 방향 그래프에서 존재하는 모든 Mother Vertex를 구하는 방법에 대해 알아본다. Existence of a Mother Vertex Mother Vertex의 존재성을 판정하는 방법은 두가지가 있다. 첫번째 방법은 각 정점에서 방문이 가능한 정점을 저장하는 bitset을 생성한다. 모든 비트가 체크된 노드가 있다면 그것은 Mother Vertex이다. DFS를 통해 bitset을 갱신한다. 주의할 것은 한번의..

2020.09.25

특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘

*LCS Longest Common Subsequence. Subsequence는 부분수열들이 꼭 연속하지 않아도 된다. 예를 들어 두 수열 A,B가 있다 하자. A = 1 5 3 4 2 6 5 B = 1 6 3 2 3 5 A와 B의 부분 수열은 {1}, {3}, {1,2} 등 여러가지가 있다. A와 B의 LCS는 {1,3,4,5}이고 그 길이는 4이다. A의 길이를 n, B의 길이를 m이라 할 때 다이나믹 프로그래밍을 이용해 O(nm)의 시간에 LCS(A,B)를 구할 수 있다. 이는 잘 알려져 있는 알고리즘이므로 쉽게 설명된 글이 많다. 이 글에서는 특정 상황에서 빠르게 LCS를 구하는 방법에 집중한다. 또한 앞으로 LCS를 구하는 것을 LCS의 길이를 구하는 것과 동일하게 취급한다. *특정 조건에서 ..

2020.09.25

Convex Hull과 Sorting의 관계

정렬 문제를 Convex Hull 문제로 환원하는 방법을 소개합니다. Convex Hull 문제를 정렬 문제로 환원할 수 있다는 것은 널리 알려져 있는 사실이다. Graham Scan알고리즘은 점들을 각도 순으로 정렬한 뒤 한 번의 스캔을 통해 Convex Hull을 구하는 알고리즘이기 때문이다. 곧, 다항 시간 내에 Convex Hull 문제를 점들을 정렬하는 문제로 환원할 수 있다. 여기서는 정렬 후에 이루어지는 스캔 (O(N))이 변환 시간이 된다. 다음과 같이 나타낸다. 여기까지는 Convex Hull과 다항식 시간 변환의 개념을 안다면 누구나 알 수 있는 사실이다. 한 발 더 나아가보자. 정렬 문제를 Convex Hull을 구하는 문제로 변환할 수 있을까? 즉, Convex Hull을 구하는 알..

2020.08.15