[자료구조] 다항식 연산 구현

다항식이란 여러 개의 항으로 이뤄진 방정식을 말한다. 수학 시간이 아니기 때문에 자세한 설명은 생략하겠다...
 
다항식 간에 덧셈은 차수가 같은 항의 계수끼리를 더하는 식으로 진행된다. 가령 (1 + 2x + 2x^2) , (2 + 4x + 5x^2) 이 두 다항식을 더하면 차수가 같은 항의 계수끼리 덧셈이 진행되어 3 + 6x + 7x^2이 된다.
 
다항식 간의 곱셈은 말로 설명하기는 좀 빡세고 식으로 설명하겠다. 가령 (1+2x), (3 + 3x^2) 라는 두 다항식의 곱셈은 
1(3+3x^2) + 2x(3+3x^2) = 3 + 3x^2 + 6x + 6x^3 = 3 + 6x + 3x^2 + 6x^3이다. 
 
cf) ^(caret) 기호는 거듭제곱을 의미한다.
 
 

다항식 구현 원리

일단 ADT를 먼저 살펴보자.

#pragma once

class Polynomial
{
public:
	Polynomial(int max_degree = 100);
	Polynomial(const Polynomial& poly);
	~Polynomial();
	
	int MaxDegree();
	void NewTerm(const float coef, const int exp);
	Polynomial Add(const Polynomial& poly);
	Polynomial Mult(const Polynomial& poly);
	float Eval(float x);
	void Print();

private:
	int capacity_ = 0; // 항상 모든 항(term)들이 다 차 있는 것은 아니기 때문에 size 대신 capacity 사용
	float* coeffs_ = nullptr;
};

생성자가 2개 보이고 그 밑으로 여러가지 함수가 보인다.
 
이름만으로 기능을 대충 추측하자면 newTerm은 새로운 항을 입력받는 함수 같고 add,mult는 다항식 연산을 해주는 함수로 보인다. eval은 x에 특정한 수를 넣어주고 그 값을 계산해서 반환하는 함수 같고 print는 newTerm으로 입력받은 항들을 한번에 출력해주는 함수로 보인다.
 
항을 추가로 입력(NewTerm)받는 부분을 보면 입력 파라미터가 2개인데 각각은 항의 차수와 계수이다. 이제 구현을 해보자.......
 
 

구현

#include "Polynomial.h"

#include <cassert>
#include <iostream>
#include <math.h> // std::powf()

using namespace std;

Polynomial::Polynomial(int max_degree)
{
	assert(max_degree > 0);

	capacity_ = max_degree + 1;
	coeffs_ = new float[capacity_];

	for (int i = 0; i < capacity_; i++)
		coeffs_[i] = 0.0f;
}

Polynomial::Polynomial(const Polynomial& poly)
{
	this->capacity_ = poly.capacity_;
	coeffs_ = new float[capacity_];
	for (int i = 0; i < capacity_; i++)
		coeffs_[i] = poly.coeffs_[i];
}

Polynomial::~Polynomial()
{
	if (coeffs_) delete[] coeffs_;
}

int Polynomial::MaxDegree()
{
	return this->capacity_ - 1;
}

void Polynomial::NewTerm(const float coef, const int exp)
{
	assert(exp < capacity_);
	coeffs_[exp] = coef;
}

Polynomial Polynomial::Add(const Polynomial& poly)
{
	assert(poly.capacity_ == this->capacity_);

	Polynomial temp(this->MaxDegree());
	for (int i = 0; i < this->capacity_; i++)
	{
		if (poly.coeffs_[i] != 0 || this->coeffs_[i] != 0)
		{
			temp.NewTerm(coeffs_[i] + poly.coeffs_[i], i);
		}
	}
	return temp;
}

Polynomial Polynomial::Mult(const Polynomial& poly)
{
	assert(poly.capacity_ == this->capacity_); 

	Polynomial temp(this->MaxDegree());
	for (int i = 0; i < this->capacity_; i++)
	{
		if (coeffs_[i] != 0.0f)
		{
			for (int j = 0; j < poly.capacity_; j++)
			{
				if (poly.coeffs_[j] != 0.0f)
				{
					temp.coeffs_[i + j] += coeffs_[i] * poly.coeffs_[j];
				}
			}

		}
	}
	return temp;
}

float Polynomial::Eval(float x)
{
	float temp = 0.0f;
	for (int i = 0; i < capacity_; i++)
	{
		if (coeffs_[i] != 0.0f)
		{
			temp += coeffs_[i] * powf(x, i);
		}
	}
	return temp;
}

void Polynomial::Print()
{
	bool is_first = true; 

	for (int i = 0; i < capacity_; i++)
	{
		if (coeffs_[i] != 0.0f)
		{
			if (!is_first)
				cout << " + ";

			cout << coeffs_[i];

			if (i != 0) 
			cout << "*" << "x^" << i;

			is_first = false;
		}
	}
	cout << endl;
}

딱 3가지만 유의깊게 지켜보면 된다.
 
1) 생성자 부분에서 capacity(수용력)값 만큼 공간을 동적으로 할당 받고 그 공간을 0으로 초기화하는 것을 볼 수 있다.
 
2) 항을 추가할 떄마다 차수를 인덱스 번호로 쓰고 계수를 인덱스 값으로 저장한다. 반복문을 돌 때 인덱스 값이 0이 아님을 확인하는 이유가 그것 떄문이다. 항이 몇 개 안되는데 capacity는 100이다. 연산량이 쓸데없이 많아진다는 생각이 들 수 있는데 합리적인 생각이다.
 
3) 다항식의 덧셈과 곱셈의 원리를 서두에 소개했는데 이 원리를 어떠한 식으로 구현했는지는 ADD 함수와 MUTI 함수를 보면 알 수 있다.