Processing math: 100%

$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$

'알고리즘 공부/Mathematics' 카테고리의 글 목록::::Gratus' Blog

Gratus' Blog

"알고리즘 공부/Mathematics" 관련 글 3

메르텐스 함수 (Mertens Function) 와 그 빠른 계산 (Xudyh Sieve)

알고리즘 공부/Mathematics 2020. 5. 1. 04:23

메르텐스 함수 (Mertens Function) 은 뫼비우스 함수 (Mobius Function) 으로부터 정의되는, 매우 재밌는 성질을 갖는 함수이다. 1. Mobius Function / Mertens Function의 정의 먼저, 간단히 정의를 살펴보자. 정의. Mobius Function 다음과 같은 뫼비우스 함수를 정의한다.

$\mu(n) =\begin{cases} 0, & ^\exists d \in \mathbb{N}, d > 1 \text{ such that } d^2 | n\\ (-1)^k, & n = p_1 p_2 p_3 \dots p_k \end{cases}$ https://gratus907.com/43?category=869407 한참 예전에 이런 포스팅을 했었는데, 여기에서 뫼비..

FFT (Fast Fourier Transform) 와 실수오차

알고리즘 공부/Mathematics 2020. 2. 27. 21:31

FFT (Fast Fourier Transform) 은 기본적으로, 다항식의 계수 표현 (Coefficient form. 정식 용어는 아닌거 같지만 어디선가 본 말이다) 과 점 표현 (Point-value form) 을 오가는 알고리즘이다. FFT를 이용하면, 두 다항식의 곱을

$O(n \log n)$ 에 계산하는 등 일반적으로는 할 수 없는 연산들을 빠르게 수행할 수 있기 때문에 다양한 용도로 사용할 수 있고, PS에서는 나름 고인물 알고리즘의 시작(?) 같은 느낌으로 생각되는 것 같다. ICPC Regional에도 가끔 나오는 것 같고...물론 요즘같이 다들 고여버린 때는 별로 의미가 없지만 ㅋㅋㅋ FFT가 왜 작동하는지, 어떻게 작동하는지, 어떤 일들을 할 수 있는지는 다양한 자료를 통해 공부할 수..

유클리드 호제법

알고리즘 공부/Mathematics 2019. 8. 8. 22:50

유클리드 호제법 (Euclidean Algorithm) 은 두 자연수의 GCD (Greatest common divisor, 최대 공약수) 를 구하는 가장 일반적인 알고리즘이다. GCD를 구하는 이유야 수없이 많을 수 있고, 특히 PS를 할때는 오만 이상한 이유로 GCD를 구해야 하는데 (...) 코드로는 재귀로 짜면 함수 자체는 한 줄이면 된다. 대충

$\texttt{int gcd(int a, int b)}$ 를 선언하고,

$\texttt{return a%b?gcd(b,a%b):b;}$ 해주면 알아서 잘 구해주고, 어차피 이게 느려서 안되는 경우는 잘 없지만 inline을 붙이든 반복문으로 구현을 하든 할수도 있다. GCC 컴파일러를 사용한다면, 직접 구현할 필요도 없다. $\texttt{__gcd(a..

이전 1 다음

티스토리툴바