증명

BOJ-10803 정사각형 만들기(증명)

https://www.acmicpc.net/problem/10803 10803번: 정사각형 만들기 두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를 www.acmicpc.net dp로 모든 n, m에 대하여 구하면 TLE를 받기에 뭔가의 조건으로 시간복잡도를 줄여야한다. 대부분의 풀이는 $WLOG \ n \leq m$ 에 대해 $ 3n \leq m$의 조건에 대하여 $dp[n][m] = dp[n][m-n] + 1$을 해주고 있다. 이렇게 타이트한 조건에 대해선 증명하지 못하였고 정당성에 대해서도 잘 모르겠다. 찾은 조건은 $m >= \frac{n^2}{3}$ 에 대하..

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

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

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