전체 글

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..

백준 및 코드포스

2021/6 - 백준 첫 시작(한달동안 기초문제들만 슬쩍봄) 2021/12 ~ 현재(2022/4/1기준) 백준 5개월, 푼 문제 420개, 플레티넘 2 20점 2021/2/8 codeforces 첫 시험 2021/4/1 기준 contest 9회 참여, 레이팅은 1484... 아직은 푸는 속도와 실수에 발목을 많이 잡히는 것 같다. virtual이 도움이 될까 싶은 마음에 안하고 있었는데 최근에 한번 쳐본 후로 생각이 바뀌어서 앞으로 virtual을 가끔씩 해보려고 한다. 2022/4/10 극심한 슬럼프 요새 문제들이 손에 잡히지 않고 글씨가 둥둥 떠다니는 느낌이다. 실수도 너무 많고, 실수를 한 문제를 디버깅하는게 너무나도 귀찮은 상태다. 대충 머리속으로 알고리즘을 생각한후 TLE가 날 것 같으면 sub..

백준 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))$으로 전체의 쿼리에 ..