Processing math: 38%

본문 바로가기

안즈와 소소한 취미생활

ANZ1217

Notice

안녕하세요. ANZ입니다.

Recent Posts

Popular Posts

Recent Comments

Link

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

알고리즘/수학

알고리즘/수학 2021. 3. 14. FFT 최대 차수가

$n$ 인 두 다항식

$A, B$ 가 있습니다. 두 다항식의 곱

$A \times B$ 을 계산하는 작업은 일반적으로

$O(n^2)$ 의 시간복잡도를 가지게 됩니다. 이 작업을 무려

$O(n\log n)$ 에 할 수 있는 FFT 알고리즘에 대해 알아봅시다. 먼저, 다항식을 나타내는 2가지 방법에 대해 알아봅시다.

$n$ 차 다항식을 나타낸다고 생각해 봅시다. 먼저, 일반적으로

$n$ 차 다항식의

$n+1$ 개의 계수를 차례대로 늘어놓는 방법이 있습니다.

$ax^2+bx+c \rightarrow \{c,b,a\}$

$i$ 번째 원소는

$i$ 차 항을 나타내기 때문에 역순입니다. 이를 Coefficient Representation이라고 합니다. 두 번째로, 이 다항식에 \..

알고리즘/수학 2021. 3. 13. 스프라그–그런디 정리 게임 이론에 대해 알아봅시다. 하나의 게임은 몇 명의 참가자와 참가자들이 할 수 있는 행동, 그리고 이 행동 조합에 따라 받게 되는 보상으로 구성됩니다. 이러한 게임 중 여기에서 다루고자 하는 게임은 다음과 같은 조건을 만족하는 게임입니다. 1. 두 명의 참가자가 진행합니다. 2. 두 사람이 차례를 가지고 번갈아가며 진행합니다. (순차적 게임) 3. 모든 참가자가 게임에 대한 모든 정보를 공유합니다. (완전 정보 게임) 4. 자신의 차례에 할 수 있는 행동이 하나도 없으면 패배합니다. (일반 게임) 5. 게임이 무한히 진행되지 않습니다. 이런 복잡한 조건들을 만족하는 게임이 대체 뭐가 있냐고 생각하실 수 있지만, 이를 만족하는 간단한 게임이 있습니다. 바로 "베스킨라빈스 31"이라는 게임입니다. 두 명이..

알고리즘/수학 2021. 3. 11. 기초 정수론2 페르마의 소정리

$p$ 가 소수이고,

$\gcd(p, a) = 1$ 일 때

$a^{p-1} \equiv 1 \mod p$ 앞선 글에서 모듈러 역원을 구하는데 확장 유클리드 알고리즘을 이용할 수 있다는 사실을 알았습니다. 그런데 모듈러가 소수라면, 조금 더 간단하게 모듈러 역원을 구할 수 있습니다. 페르마의 소정리에 따르면,

$p$ 가 소수일 때

$p$ 와 서로소인 임의의

$a$ 의 모듈러 역원은

$a^{p-2}$ 입니다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수

$K$ 가 주어졌을 때 이항 계수

$\binom{N}{K}$ 를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.ne..

알고리즘/수학 2021. 3. 11. 기초 정수론1 PS에 필요한 기초적인 정수론을 다뤄 봅시다. 저는 수학을 잘 하지는 못합니다. 그래서 이 글에서는 각 주제에 해당하는 내용에 대해 간단히 설명만 하고, 엄밀한 증명은 하지 않을 예정입니다. 단순히 "이런 것들이 있다" 정도로만 봐 주시면 좋을 것 같습니다. 자세한 내용이나 증명은 다른 글을 참조해주세요. 유클리드 알고리즘 두 양의 정수

$A, B$ 의 최대공약수를 구해봅시다.

$\gcd(A, B) = g$ 라고 하면, 다음과 같이 나타낼 수 있습니다.

$A = ga, B = gb$

$a$ 와

$b$ 는 서로소입니다.

$A$ 를

$B$ 로 나눴을 때 몫과 나머지를 각각

$q, r$ 이라고 해 봅시다.

$A = Bq+r$ 위의 식을 대입해 봅시다.

$ga = gbq+r$ $$r = ..

이전 1 다음

티스토리툴바