Fast Fourier Transform을 이용한 빠른 다항식 곱셈 공부하기

1. 두 다항식의 곱셈 다항식 $f(x) = a_{0}x^{0} + a_{1}x^{1} + ... + a_{n-1}x^{n-1}$과 $g(x) = b_{0}x^{0} + b_{1}x^{1} + ... + b_{n-1}x^{n-1}$의 곱셈은.. $f(x)g(x) = a_{0}b_{0}x^{0} + (b_{0}a_{1} + a_{1}b_{0})x^{1} + ... + a_{n-1}b_{n-1}x^{2n-2}$로 나타날 것이다. 다항식을 각각 계수만을 가진 길이가 n인 벡터 A = [a0,a1,...,an-1], B = [b0, b1, ... , bn-1]로 나타낸다고 할때, 두 다항식의 곱셈은 길이가 2n-1인 벡터 C = [c0,c1,...,c(2n-2)]로 나타나며, $$c_{i} = \sum_{j=0..

• format_list_bulleted 대수학
• · 2023. 8. 29.
• textsms

키타마사 법(kitamasa method, きたまさ法)에 대한 공부

1. 키타마사 법(kitamasa method) 수열 $a_{n}$의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다. $$a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$$ 이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다. $$a_{n} = a_{n-1} + a_{n-2}, w_{1} = w_{2} = 1, k = 2$$ 이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다. https://deepdata.tistory.com/760 행렬을 이용한 피보나치 수열 문제의 해법 1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + ..

• format_list_bulleted 대수학
• · 2023. 8. 27.
• textsms

다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기

1. 다항식의 곱셈 두 다항식의 곱셈은 구현하는 방법이 많이 있지만... 당장은 어려우니 일단 $O(k^{2})$으로 naive하게 구현 해보자. 다항식은 각 항의 계수를 배열에 저장하면 되는데 $f(x) = 2x^{2} + x + 1$이라고 한다면, a = [1,1,2]로 저장하면 된다. 곱셈하고자 하는 다항식이 $g(x) = x + 5$라고 한다면 b = [5,1]이고 두 다항식의 곱셈은 $f(x)g(x) = 2x^{3} + 11x^{2} + 6x + 5$로 [5,6,11,2]가 나와야한다. f(x)가 len(a)-1차수 다항식이고 g(x)가 len(b)-1차수 다항식이면, f(x)g(x)는 len(a)+len(b)-2차수 다항식이다. 위에서 len(a) = 3, len(b) = 2이고 각각 2차 1..

• format_list_bulleted 대수학
• · 2023. 8. 26.
• textsms

파이썬 알고리즘 기본기 곱셈 연산에서 주의할 점 배우기(세그먼트 트리 문제)

1. 문제 5676번: 음주 코딩 (acmicpc.net) 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 특정 구간의 수열의 곱이 양수인지 음수인지 0인지 판단하거나 특정 인덱스의 원소를 바꾸는 쿼리를 수행하는 문제 2. 곱셈의 시간복잡도 매우 큰 수를 곱할수록 프로그램의 시간복잡도가 높아진다. 이게 몇번만 연산하면 별로 차이 없어보이지만 10만번이나 반복연산해야한다면, 눈에띄게 느려진다 매우 큰 4개의 수를 곱하는 과정을 10만번 반복했는데 평균적으로 0.03초 걸린다면... 단순히 1,2,3,4 4개..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 10.
• textsms