전체 글20 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}$ 에 대하.. 2022. 5. 31. Fast Fourier Transform(FFT) - 고속 푸리에 변환 # About Fast Fourier Transform is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. (reference) # Concept .. 2022. 5. 15. 백준 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에 넣어준후, 각 정.. 2022. 4. 26. 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.. 2022. 4. 22. 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;.. 2022. 4. 22. 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의 정의부터 보도록하자. 유클리드 공간에서 유계 닫힌집합과 점렬 콤팩트 공간의 개념이 일치한다 유클리드 공간에서 유계의 닫힌 집합이란 .. 2022. 4. 21. 이전 1 2 3 4 다음 320x100