다항식의 각 항별 계수가 배열 형태로 주어져 있을 때, 이 두 다항식을 곱하는 프로그램을 작성해야 합니다. 먼저 예제를 통해 문제를 자세히 살펴보겠습니다.
예제
입력
A = [1, 2, 3, 4]
B = [4, 3, 2, 1]
출력
4x6 + 11x5 + 20x4 + 30x3 + 20x2 + 11x1 + 4
여기서 배열 A는 다항식 4x³ + 3x² + 2x + 1의 계수를, 배열 B는 다항식 x³ + 2x² + 3x + 4의 계수를 나타냅니다. 배열은 낮은 차수부터 높은 차수 순으로 저장되며, 두 다항식을 곱하면 최대 6차까지의 항을 가지는 새로운 다항식이 만들어집니다.
알고리즘
곱할 두 다항식 A와 B를 초기화합니다.
m개 항과 n개 항을 가진 두 다항식의 곱은 최대 (m+n-1)개의 항을 가지므로, 길이가 m+n-1인 새로운 배열을 생성하고 모든 값을 0으로 초기화합니다.
이중 반복문으로 두 다항식의 모든 항 쌍을 순회합니다.
첫 번째 다항식의 한 항 A[i]를 가져와 두 번째 다항식의 모든 항 B[j]와 차례대로 곱합니다.
A[i]와 B[j]를 곱한 결과는 지수가 i+j인 항에 해당하므로, 결과 배열의 productPolynomial[i+j] 위치에 누적하여 저장합니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int *multiplyTwoPolynomials(int A[], int B[], int m, int n) {
int *productPolynomial = new int[m + n - 1];
for (int i = 0; i < m + n - 1; i++) {
productPolynomial[i] = 0;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
productPolynomial[i + j] += A[i] * B[j];
}
}
return productPolynomial;
}
void printPolynomial(int polynomial[], int n) {
for (int i = n - 1; i >= 0; i--) {
cout << polynomial[i];
if (i != 0) {
cout << "x^" << i;
cout << " + ";
}
}
cout << endl;
}
int main() {
int A[] = {1, 2, 3, 4};
int B[] = {4, 3, 2, 1};
int m = 4;
int n = 4;
cout << "First polynomial: ";
printPolynomial(A, m);
cout << "Second polynomial: ";
printPolynomial(B, n);
int *productPolynomial = multiplyTwoPolynomials(A, B, m, n);
cout << "Product polynomial: ";
printPolynomial(productPolynomial, m + n - 1);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
First polynomial: 4x^3 + 3x^2 + 2x^1 + 1
Second polynomial: 1x^3 + 2x^2 + 3x^1 + 4
Product polynomial: 4x^6 + 11x^5 + 20x^4 + 30x^3 + 20x^2 + 11x^1 + 4
시간 복잡도 분석
이 알고리즘은 첫 번째 다항식의 각 항을 두 번째 다항식의 모든 항과 한 번씩 곱하므로, 시간 복잡도는 O(m×n)입니다. 여기서 m과 n은 각각 두 다항식의 항 개수입니다. 매우 큰 다항식을 다뤄야 한다면 FFT(고속 푸리에 변환)를 활용하면 O(n log n)의 시간 복잡도로 더 빠르게 곱셈을 수행할 수 있습니다.