전체 글110 푸리에 변환(Fourier Transform) 푸리에 변환 푸리에 변환이란 시간에 대한 신호 함수를 주파수에 대한 식으로 변환하는 것을 말한다. 성공적으로 변환을 한다면 노이즈와 여러 주파수가 섞인 신호에서 특정 주파수를 추출해낼 수 있다. 이것 외에도 푸리에 변환의 그 성질을 이용해서 어떤 연산을 더욱 쉽게 풀어쓸 수도 있다. 푸리에 변환의 깊은 뜻 말고 단순히 문제풀면서 겪었던 몇 가지만 적어보면 다음과 같다. convolution 두 수열의 convolution을 구할때 일반적으로 n^2의 연산이 필요로 한다. fourier transform으로 변환 후 convolution을 빠르게 할 수 있다. 큰 수의 곱셈 곱셈은 일반적으로 자리수의 제곱에 해당하는 연산을 필요로 한다. fourier transform으로 변환 후 곱셈을 빠르게 할 수 있.. 2019. 10. 17. 오일러 피 함수(Euler's phi function) Euler's phi function 오일러 피(파이) 함수 $\phi (n)$ 란 1과 n까지의 정수 중 n과 서로소인 개수를 뜻한다. 거부감 없이 정의는 매우 쉽다. int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); } int getEulerPhiFunc(int n){ int cnt = 0; for(int i = 1; i < n; i++){ if(gcd(n, i) == 1) cnt++; } return cnt; } 대충 예외 생각 안 하고 구현하면 위와 같이 구하면 된다. 이 방법은 $ \phi (n) $ 의 성질을 하나도 안 따져보고 구했으니, 더 좋은 방법을 위해 성질을 알아보자. 일단 가장 간단하게 유추할 수 있는 것이 있다. $$ \phi(p).. 2019. 10. 17. 모듈러 나눗셈 Modular 사칙연산만큼 친숙한 모듈러지만 연산은 사칙연산만큼 심플하지는 않다. 정의 자체가 나눗셈을 한 후에 나머지를 가리키는 뜻이니 나눗셈 이상의 매력이 있다. 그럼 한번 사칙연산과 모듈러의 관계를 정리해보자. $$ \begin{align} (a + b)\ \%\ M & = ((a\ \%\ M) + (b\ \%\ M))\ \%\ M \\ (a - b)\ \%\ M & = ((a\ \%\ M) - (b\ \%\ M) + M)\ \%\ M \\ (a \times b)\ \%\ M & = ((a\ \%\ M) \times (b\ \%\ M))\ \%\ M \\ (a\ /\ b)\ \%\ M & = ((a\ \%\ M)\ /\ (b\ \%\ M)\ \%\ M \cdots ? \end{align} $$ 덧셈.. 2019. 10. 17. 이전 1 ··· 30 31 32 33 34 35 36 37 다음
