Math

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}$ 에 대하..

Nested Interval Property - 폐구간 수렴 정리

# Definition of the Nested Interval Let $(I_{n})_{n\in \mathbb {N}}$ be a sequence of closed intervals of the type $I_{n}=\left[a_{n},b_{n}\right]$, where $\mid I_{n} \mid \colon = b_{n} - a_{n}$ denotes the length of such an interval. One can call $(I_{n})_{n\in \mathbb {N}}$ a sequence of nested intervals, if 1. $\quad \forall n\in \mathbb {N} :\;\;I_{n+1}\subseteq I_{n}$ 2. $\quad \forall \va..

Monotone Convergence Theorem - 단조 수렴 정리

# Definition In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the convergence of monotonic sequences (sequences that are non-decreasing or non-increasing) that are also bounded. Informally, the theorems state that if a sequence is increasing and bounded above by a supremum, then the sequence will converge to the supremum;..

Bolzano–Weierstrass theorem - 볼차노-바이어슈트라스 정리

# Definition Bolzano–Weierstrass theorem — result about convergence in a finite-dimensional Euclidean space Rn. The theorem states that each bounded sequence in Rn has a convergent subsequence. (reference) 볼차노-바이어슈트라스 정리란 유클리드 공간에서 유계 닫힌집합과 점렬 콤팩트 공간의 개념이 일치한다는 정리이다. (reference) 해석학과 위상수학에서 매우 중요하며 많이 쓰이는 정리이다. Definition의 정의부터 보도록하자. 유클리드 공간에서 유계 닫힌집합과 점렬 콤팩트 공간의 개념이 일치한다 유클리드 공간에서 유계의 닫힌 집합이란 ..

Analysis - 해석학(1)

Definition 정의 1. 집합 집합이란 문맥상 추정이 가능한 것들의 집합이며 이는 소속성 질문에 대답할 수 있다는 것을 뜻한다. 정의 2. 집합의 외연적정의, 내포적 정의 Denotation, Connotation 외연적 정의： 처음의 원소부터 일정 개수의 원소를 열거, 가능하다면 일반항 $a_{n}$의 요소를 표현하고 나머지는 $\ldots$로 표현하는 경우가 많다. 특별히 영소문자의 경우 $\sum$ = $\left\{a,b,c,...,z\right\}$ 로 표기 하는 경우가 있다. 내포적 정의： 집합의 요소가 만족하는 성질을 표현한 것이다. 정의 3. 부분집합 집합 $X$의 모든 요소가 집합 $Y$의 요소일때 집합$X$는 집합 $Y$의 부분집합이라고 하며 다음과 같이 표현한다. $X \subs..