PS 이야기

차수가 $n$인 다항식 $f(x) = c_0 + c_1x^1 + c_2x^2 + \cdots + c_nx^n (c_n \ne 0)$가 있다. 그리고 차수 $m$인 다항식 $g(x) = d_0 + d_1x^1 + d_2x^2 + \cdots + d_mx^m (d_m \ne 0)$이 있다. 이를 다항식 $q$와 $r$을 이용하여, $f(x) = g(x)q(x) + r(x)$라고 나타내 보자. $r(x)$의 차수가 $m$보다 작은 경우, $f$를 $g$로 나눈 몫을 $q$, 나머지를 $r$이라고 정의한다. 다항식 $q$의 차수는 $n-m$이다. 다항식의 나눗셈을 교과과정에서 배운대로 구현한다면 $O(nm)$ 시간복잡도가 된다. 이를 좀 더 빠르게 하는 방법에 대해서 알아보자. $\textrm{Rev}(f)$를..