algorithm

백준 1199번 - 오일러 회로

https://www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net # Approach) 오일러 회로를 구성하는 알고리즘, Hierholzer's Algorithm에 대해 배우는 문제이다. # Logic) Hierholzer's Algorithm을 그대로 적용하자. TLE를 피하기 위하여 본 포스트에서는 인접행렬대신 인접리스트를 이용하여 구현할것이다. 1. 간선의 정보를 저장해준다. 각각의 간선의 정보를 간선의 리스트 edges에 넣어준후, 각 정..

Flow network - 네트워크 플로우

# Definition A flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge reference 플로우 네트워크 G는 모든 간선이 용량과 유량의 속성을 가지는 그래프이며 유량은 항상 용량을 초과할 수 없다. # Term Definition ## Flows ## flow를 정의하는 방법(notation)은 다양하다. 이 중 가장 직관적이며 대표적인 의사-유량(pseudo-flow라서 대충 의사-유..

백준 1006번 - 습격자 초라기

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net # Approach) 타일링문제와 상당히 흡사하다. 고로 DP를 떠올려보자. First Try(Failed) # Definition) $dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i$, $and \ outer \ j$ $in[i] :$ $cost \ of \..

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