fft 썸네일형 리스트형 <자료구조 알고리즘> FFT를 이용한 다항식 곱셈 알고리즘 다항식 곱셈은 수학에서 아주 기본적으로 하는 연산 중에 하나이다. $$A(x) = 5x+2$$ $$B(x) = x^2+2x+3$$ 이 두식을 곱한 C(x)를 구한다고 하면 $$C(x) = (5x+2)(x^2+2x+3) \\ = 5x \times x^2 + 5x \times 2x+2\times x^2 + 5x \times 3+2 \times 2x + 2 \times 3 = 5x^3 + 14x^2 + 19x + 6$$ 이렇게 쉽게 계산할 수 있다. 하지만 컴퓨터로 짜려면 어떻게 해야 할까? 다항식을 나타내는 방법에는 대표적으로 coefficient representation과 value representation 이 있다. coefficient representation으로 위의 A(x)와 B(x)를 나타내.. 더보기 이전 1 다음