Categories
Max-flow min-cut theorem - 최대 유량 최소 컷 정리
# Definition the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. reference $flow(s,t)_{max} = cut(s,t)_{min}$ 그래프 $G$에서 최대유량 $flow(s,t)_{max}$는 항상 source와 sink의 최..
Floyd-Warshall Algorithm - 플로이드 워셜 알고리즘
# Expression $ \forall u,v \in G: \ \ cost(u,v)$ 그래프 G에 대해서 모든 정점간의 최소 비용을 계산할때 쓰이며 음의 가중치 간선이 있어도 동작한다. 이러한 최소 비용 문제를 일반적으로 Shortest Path Problem 으로 분류한다. # Algorithm let cost[V+1][V+1] // cost[i][j]: cost of the shortest path from i to j //init for(i: 0~V) for(j: 0~V) if(i == j) cost[i][j] = 0 else cost[i][j] = w[i][j] ? w[i][j] : INF //relaxation for(mid: 0~V) for(start: 0~V) for(end: 0~V) if..
Euclidean Algorithm - 유클리드 호제법
# Definition $ a = bq + r(0 \le r = b,$ $GCD(a, b) = GCD(a-b, b) $ $g=GCD(a,b),$ $ \ a = gA,$ $ \ b =gB$ 라 두자. $ GCD(a-b, b) $ $= GCD(g(A-B), gB) $ 이기에 A-B와 B가 서로소임을 보이면 Lemma 1은 증명된다. 귀류법으로 $ GCD(A-B, B) = g_{A,B},$ $A-B = g_{A,B}M,\ B $ $= g_{A,B}N,\ g_{A,B} \neq 1$ 를 만족하는 $\exist..
백준 1395번 - 스위치
https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Time Complexity) 업데이트를 진행할때 s~t구간의 스위치를 모두 토글해야한다. 각 원소를 하나하나 토글한다면 세그먼트 트리를 사용했을때 시간복잡도는최대 한번의 업데이트에 $O(log(n))$으로 전체의 쿼리에 ..
백준 3653번 - 영화 수집
https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Point) DVD의 번호를 기준으로 세그먼트 트리를 만들면 로직이 꼬이기때문에 DVD 컬렉션상의 특정 위치의 DVD의 존재 유무를 기준으로 잡는 것이 좋다. DVD 하나를 빼서 맨 위로 올리는 것을 '액션'이라고 하자. 트리의 원본배열의 크기(구간합이 ..