junk's Blog

「✈」

푸리에 변환

푸리에 급수 푸리에 변환에 대해 알아보기 전에 매우 친숙한 푸리에 급수에 대해서 먼저 알아볼 필요가 있다. 먼저, 푸리에 급수의 정의에 대해 알아보자. “유한 구간의 정의된 주기함수를 삼각함수의 급수 전개로 표현한 것” 그리고 이를 식으로 표현하면 주기가 T인 함수 f의 푸리에 급수를 다음과 같이 나타낼 수 있다. \[\begin{align*...

Posted by junk727 on March 24, 2023

N! mod P

이 글은 정말 유명한? 문제라고 할 수 있는 $\text{N}!\ \text{mod}\ p$ 문제를 다음 글을 바탕으로 공부한 내용을 정리하였다. N! mod p의 빠른 계산 $\text{N}!\ \text{mod}\ p$ 당연히 Naive 하게 구현을 시도한다면 $O(n)$이 되겠지만, 조금 창의적인 발상을 시도하면 $O(nlogn)$에 구할 ...

Posted by junk727 on March 10, 2023

개인공부 조각들

P-NP https://gazelle-and-cs.tistory.com/64 컴퓨터로 푸는 문제라는 것은 무엇일까? 문제의 엄밀한 정의는 “입력 집합과 해답 집합 사이의 어떤 관계”라고 할 수 있겠다. 그런데 수많은 형태를 지닌 문제들을 모두 고려하는 것은 쉬운일이 아니기에 입력이 참 또는 거짓인지만 다지는 결정 문제에 대해서만 생각해보...

Posted by junk727 on March 1, 2023

공부해본 미적분학

미적분학의 기본정리 FTC 1 If $f$ is continuous on $\lbrack a,b \rbrack$, then the function is define by \[F(x) := \int_{a}^{x}f(t)\ dt\] Then, \[\frac{d}{dx} \int_{a}^{x}f(t)\ dt = f(x)\] FTC 2 \[\in...

Posted by junk727 on February 27, 2023

중국인의 나머지 정리 - Chinese Remainder Theorem

중국인의 나머지 정리 - CRT 정의 $m_1,m_2,\cdots,m_n$가 쌍마다 서로소, 즉 $\gcd(m_i,m_j)=1,(i\neq j)$이면, 다음 연립 합동식 \[x\equiv a_1\ (mod\ m_1)\\ x\equiv a_2\ (mod\ m_2)\\ \vdots\\ x\equiv a_n\ (mod\ m_n)\] 은 법 $m_1,m...

Posted by junk727 on February 17, 2023

선형 점화식 - Linear Recurrence Relation

업데이트 된 글을 확인하십시오 여기로 이 글에서는 선형 점화식을 찾는 벌레캠프 알고리즘과 확장 유클리드법을 사용한 알고리즘을 다룬다. 벌레캠프 매시 - Berlekamp Massey 앞서 선형 점화식이 주어졌을 때 빠르게 계산하는 방법인 키타마사법에 대해서 알아보았다. 여기서 더 나아가 선형 점화식을 찾아내는 벌레캠프 매시 알고리즘에 대해 알아...

Posted by junk727 on February 16, 2023

키타마사법 - Kitamasa Method

선형 점화식 - Linear Recurrence Relation 선형 점화식이란 다음과 같이 상수 계수를 가진 몇 개의 항의 선형 결합으로 구성된 점화식을 말한다. \[a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ma_{n-m}\] 이미 계수가 결정되어있을 때 $n$번째 항을 계산하는 방법은 다양한데, naive하게 구현하면 $...

Posted by junk727 on February 16, 2023

춤추는 링크 - Dancing Links

이 글에서는 Exact Cover 문제들과 알고리즘 X, 그리고 최적화 테크닉 Dancing Links에 대해 다룬다. Exact Cover Exact Cover Problem Exact Cover 문제의 사전적 정의는 다음과 같다. 조합론적 관점에서 보자면 주어진 집합 $X$의 부분 집합들을 원소로 가지는 집합 $S$가 주어졌을 때, $X$의...

Posted by junk727 on February 15, 2023

모듈러 역원 - Modular Inverse

유클리드 알고리즘 - Euclidean Algorithm 정의 두 양의 정수 $a,b\ (a<b)$에 대하여 \[b=aq_1+r_1 \\ a=r_1q_2+r_2 \\ r_1=r_2q_3+r_3 \\ \vdots \\ r_{n-2}=r_{n-1}q_n+r_n \\ r_{n-1}=r_nq_{n+1}\] 일때, $a,b$의 최대공약수는 $r_n...

Posted by junk727 on February 13, 2023

Hello World!

Hello World! Starting a PS blog on github! 1 2 3 4 5 6 7 8 #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; return 0; }

Posted by junk727 on February 12, 2023