junk's Blog

「✈」

푸리에 변환 3

어느새 3편이다. 이번 글에서는 Online FFT에 대해 집중적으로 다루고 싶다. 사실 그 전에 cubelover님의 블로그를 읽다가 XOR convolution을 FFT로 하는 방법에 대해 알게 되었는데, 이 부분을 조금 알고 넘어가면 좋을 것 같아 짧게 다뤄보도록 하겠다. XOR Convolution 나중에 쓸게요 Online FFT 일반...

Posted by junk727 on July 10, 2024

푸리에 변환 2

지난 푸리에 변환 글에서 헛소리를 남발했던 부분들을 몇개 발견하였고, 수정도 할 겸 최근에 조금 더 공부한 내용들을 정리해보고자 한다. 이번 글은 수학적인 내용보다는 실제 PS에서 활용되는 부분 위주이다. 우선 푸리에 변환 글 밑에 추가된 몇가지의 자문자답 내용들을 참고하면 좋을 것 같다. 이제 대충 푸리에 변환이 무엇인지 이해했고, 푸리에 급수에...

Posted by junk727 on July 7, 2024

고유값과 고유벡터

Eigenvalue & Eigenvector 행렬의 고유값과 고유벡터 수학적 정의는 다음과 같다. 행렬 $A$를 선형변환으로 보았을 때, 선형변환 $A$에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터를 고유벡터, 그 상수배 값을 고유값이라고 한다. 이때, 이는 $A$가 정방행렬일 때만 정의된다. \[Ax=\lambda x...

Posted by junk727 on September 11, 2023

Kirchhoff

Cayley’s Formula Theorem 완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다. Proof $K_n$의 스패닝 트리의 개수를 $T_n$이라고 하자. 이제 더블 카운팅을 이용하여 “방향성을 추가한 간선으로 구성된 스패닝 트리의 개수”를 세볼 것이다. 조금 더 풀어서 설명해보자면 아무것도 없는 그래프에서 방향성이 있...

Posted by junk727 on September 8, 2023

푸리에 해석학 - 1

How 푸리에 해석학은 어떻게 시작되었을까? 파동방정식 How to sol? 진행파 정상파 중첩 2에 초점을 맞추고 관찰 -> why? 통찰력 + 응용 사실 초기에는 2가 현의 초기 속도 및 위치가 정상파가 중첩된 매우 단순한 형태에서만 적용된다고 여겨짐 : 푸리에의 아이디어로 모든 초기조건에 대해 ㄱㄴ 밝혀짐 진행파 \...

Posted by junk727 on August 1, 2023

Inclusion-Exclusion

우선 이 글은 다음 블로그들을 참고하여 내가 공부했던 내용을 정리한 글이다! https://rkm0959.tistory.com/184 https://xy-plane.tistory.com/16 포함 배제의 원리 일반적인 포함 배제 원리의 형태 \[|\cup_{i} A_i| = \sum_{i} |A_i| - ...

Posted by junk727 on July 17, 2023

Berlekamp-Massey Algorithm

벌레캠프-매시 알고리즘 어떻게 알고리즘 이름이 벌레캠프, 아마 PS를 즐겨하다보면 한 번쯤은 들어보았을 알고리즘이다. 많은 사람들이 이를 주어진 수열로부터 가장 짧은 선형 점화식을 구하는 알고리즘이라고 알고 있을텐데, 이는 알고리즘이 가지는 의미의 반만 알고있는 것이다! 이번 글에서는 벌레캠프-매시 알고리즘의 과거와 현재, 미래를 모두 함께 살...

Posted by junk727 on July 16, 2023

중국인의 나머지 정리

CRT - Chinese Remainder Theorem 정의 $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)...

Posted by junk727 on June 5, 2023

마그마

Algebraic Structure 이항연산 집합 $S$가 존재할 때, 이항연산은 다음과 같이 정의되는 함수 $\ast$를 말한다. \[\ast : S\times S \rightarrow S\] 또는 이를 간단히 $\ast (a,b)=a\ast b$로 표현하기도 한다. 그리고 이항연산 $\ast$의 치역이 $S$의 부분집합일 때, $\ast$...

Posted by junk727 on June 5, 2023

원시근

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

Posted by junk727 on April 30, 2023