junk's Blog

「✈」

NTT

FFT를 사용하는 문제들을 풀다보면 삼각함수의 연산 때문에 생기는 실수 오차 때문에 범위가 큰 문제들에 대해서는 사용하기가 조금 부담스럽다. 또한 적당히 큰 수 p로 나눈 나머지를 계산하는 등의 문제를 만나면 건드리기가 무서워진다. 이번 글에서는 하나의 해결방법인 실수를 사용하지 않는 알고리즘, NTT에 대해 알아보고자 한다.

Posted by junk's Blog on May 2, 2023

원시근

이번 글에서는 원시근, 이산로그, 이산제곱근 등에 대해서 알아보고자 한다. 다음 블로그 글 ㅎ들을 참고하였음을 먼저 알린다. https://rkm0959.tistory.com/187 https://blog.naver.com/mindo1103/221234423247 https://blog.naver....

Posted by junk's Blog on April 30, 2023

푸리에 변환

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

Posted by junk's Blog 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 junk's Blog on March 10, 2023

개인공부 조각들

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

Posted by junk's Blog 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...

Posted by junk's Blog 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 junk's Blog on February 17, 2023

선형 점화식 - Linear Recurrence Relation

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

Posted by junk's Blog 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 junk's Blog on February 16, 2023

춤추는 링크 - Dancing Links

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

Posted by junk's Blog on February 15, 2023