전체 글

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라서 대충 의사-유..

백준 19565번 - 수열 만들기

https://www.acmicpc.net/problem/19565 19565번: 수열 만들기 문제 지문에 쓰여 있는 조건을 만족하는 가장 긴 수열을 $A$라 하자. 첫째 줄에는 $A$의 길이를 출력한다. 둘째 줄에는 $A$의 원소들을 출력한다. 이러한 수열이 여러 개일 경우 아무거나 출력한다. www.acmicpc.net # Approach) $For$ $1 \leq i < j \leq |A| $, $A_{i} \neq A_{j}$ $\lor A_{i+1} \neq A_{j+1}$ $\iff$ $ \lnot \left(A_{i} = A_{j} \land A_{i+1} = A_{j+1}\right)$ $\iff$ $\lnot \left(\left\{ A_{i}, A_{i+1} \right\} = \lef..

백준 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 \..

백준 1035번 - 조각 움직이기

https://www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net # Approach) 전형적인 완전탐색 문제이다. 1) 보드의 처음 별모양의 위치를 벡터에 넣는다. 2) 그 순서대로 각 별모양이 어디로 이동할지 정하고 다음 별모양이 선택하도록 DFS탐색을 진행해준다. # Time Complexity) 시간복잡도는 $_{25}\mathrm{P}_{5}$ $ = 5!{25 \choose 5} $ $= 6,375,600 < 10^9 $ 으로 2초안에 충분히 탐색..

Bézout's identity - 베주 항등식(Part. 1)

# Definition Bézout's identity — Let a and b be integers or polynomials with greatest common divisor a. Then there exist integers or polynomials x and y such that ax + by = d. Moreover, the integers or polynomials of the form az + bt are exactly the multiples of d. (reference) Extended Euclidean과 연결되는 정수론의 기본 정리 중 하나이다. 증명부터 해보자. $Lemma \ 1)$ $ For \ \forall a, b \in \mathbb{N} \left(a \neq 0 \l..