C++/C++ 자료구조

배열을 이용한 다항식 ADT의 표현 (Polynomial ADT using Array) - 다항식의 덧셈과 곱셈

Song 컴퓨터공학 2023. 10. 15. 05:02
반응형

 

 

배열을 이용한 매우 기초적인 다항식의 ADT 구현 코드입니다. 1차원 배열을 이용해 덧셈과 곱셈까지만 구현합니다.

다항식은 기본적으로 계수(coefficient)와 지수(exponet)로 나타낼 수 있죠. 따라서 (계수,지수)의 쌍으로 다항식의 한 term을 나타낼 수 있습니다. 다항식의 덧셈과 곱셈을 정의하려면 다항식의 몇 가지 특성을 알아야 합니다. 예를 들어 덧셈은 같은 차수에 대해서 계수를 더해야한다는 것, 각 term 들의 곱셈은 지수법칙에 의해 차수의 덧셈으로 구성되어야 한다는 점 등등.. 기본적인 내용은 생략하도록 하겠습니다.

// Polynomial.h file
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

class Polynomial {
public:
	Polynomial();
    	// 다항식 p(x)=0 생성
	Polynomial Add(Polynomial poly);
	// 다항식 *this와 ploy의 합 반환
	Polynomial Mult(Polynomial poly);
	// 다항식 *this와 ploy의 곱 반환
	float Eval(float f);
	// 다항식 *this에 f를 대입한 값을 계산해 결과 반환
};

#endif

먼저 Polynomial.h 파일에 원형을 정의합니다. #ifndef, #define 문법은 헤더파일이 중복으로 include 되는 것을 방지하기 위한 문법입니다. 위 ADT는 다항식의 ADT입니다. 하나의 다항식은 하나의 Polynomial 객체로 구성됩니다. 그러나 위의 Polynomial 클래스에는 아직은 멤버변수가 전혀 없습니다. 항을 나타내기 위한 계수와 차수 정보도 필수적으로 들어가야 하는데, 여기서 우리가 고려할 수 있는 구현 방법은 대략 3가지 정도 있습니다.

 

  1. 배열을 사용해 인덱스가 곧 차수가 되고, 해당 인덱스에 계수를 저장하는 멤버 변수를 추가하는 방법 (다항식을 표현할 수 있는 최대 차수인 MAXDEGREE 를 사용해 고정 크기의 배열을 사용)
  2. 배열을 사용해 인덱스가 곧 차수가 되고, 해당 인덱스에 계수를 저장하는 멤버 변수를 추가하는 방법 (동적 할당을 통해 불필요한 메모리를 줄이는 방법)
  3. Term 클래스를 만들고, 멤버로 Term* termArray를 추가하는 방법

 

1번의 아이디어는 정말 간단하고 직관적입니다. 아래와 같은 배열이 있다고 생각해봅시다.

이 배열의 의미하는 다항식은 p(x)=0·x4+1·x3+2·x2+0·x1+3·x0=x3+2x2+3을 뜻합니다.

이 방법으로 다항식을 저장하려면 위의 Polynomial 멤버 변수로 배열을 추가하면 됩니다.

private:
    int degree;	// degree <= MAXDEGREE
    float coef[MAXDEGREE + 1];

그런데 배열을 선언하려면 최대 크기가 몇인지를 알아야합니다. 배열을 선언할 때 [] 안에 변수가 들어가면 컴파일러가 메모리 할당을 할 수 없기 때문에 컴파일 오류가 발생하기 때문이죠. 따라서 위처럼 배열을 구현하게 되면 우리는 항상 MAXDEGREE, 즉 다룰 다항식의 최대 차원을 항상 설정해줘야하고, 만약 우리가 3차 다항식과 100차 다항식의 덧셈을 구현하고 싶다면 3차 다항식을 저장할 때도 101개의 원소를 저장하는 배열을 사용해야 합니다. 즉 불필요한 메모리 공간의 소모가 발생합니다. 또한 처리하려는 최대 다항식의 차수를 알아야 한다는 단점도 있습니다. 이러한 문제를 해결하기 위해 2번의 아이디어는 "동적할당"을 사용하는 겁니다.

private:
    int degree;
    float *coef;
}

Polynomial::Polynomial(int d){
    degree = d;
    coef = new float[degree + 1];
}

멤버 변수로 최대 차수와 계수 배열을 사용한다는 아이디어는 동일하지만, 이 때 사용되는 계수 배열을 생성될 때 최대 차수를 입력 받아 그 크기만큼만 사용하는 동적 배열을 사용하는 코드입니다. 이 방법을 사용하면 3차원 다항식과 100차원의 다항식을 더하고 싶을 때, 3차원 다항식을 저장하는 배열의 크기를 4로 만들어 불필요했던 97개의 float 공간을 절약할 수 있습니다. 

 

그러나 이 방식에도 한계가 있습니다. 이 구조는 근본적으로 희소 다항식을 표현할 때 적합하지 않습니다. q(x)=x1000+1 이라는 다항식을 저장하고 싶으면, 동적 배열이든 정적 배열이든 1001개의 float을 저장하는 배열을 사용해야만 q(x)를 표현할 수 있습니다. 이 다항식은 0이 아닌 항(non-zero term)이 2개 밖에 없는데 0인 항(zero-term)은 999개나 있습니다. 이 방법을 사용하면 필요없는 999개의 공간 소모가 생기는 것이죠. 따라서 계수 배열을 사용하고 차수를 인덱스로 사용한다는 아이디어 자체가 비효율적입니다.

 

따라서 최종적으로 채택할 방법은 0이 아닌 항만 있어도 다항식의 연산에 지장이 전혀 없으므로 non-zero term 만 저장하자는 겁니다. 그런데 그렇게 되면 배열의 인덱스를 차수로 사용하자는 아이디어를 더 이상 사용할 수 없으므로 term, 항은 계수 정보만 저장하는 것이 아닌 차수 정보도 추가적으로 저장을 해야 합니다. 그리고 각 term 마다 (계수, 차수)에 대한 정보가 필요하므로 이를 새로운 Term 클래스를 사용합니다. 또한 다항식에서 각 항단위로 연산을 진행하기 위해서는 Polynomial 클래스에서 term의 멤버에 접근이 가능해야 하기 때문에 Polynomial의 friend 클래스로 선언해야 할겁니다.

class Polynomial; // 전방 선언

class Term {
	friend class Polynomial;
private:
	float coef; // 계수
	int exp;    // 지수
};

class Polynomial {
public:
	Polynomial();
	// 다항식 p(x)=0 생성
	Polynomial Add(Polynomial poly);
	// 다항식 *this와 ploy의 합 반환
	Polynomial Mult(Polynomial poly);
	// 다항식 *this와 ploy의 곱 반환
	float Eval(float f);
	// 다항식 *this에 f를 대입한 값을 계산해 결과 반환
private:
	Term* termArray; // 0이 아닌 항들만 저장하는 배열
	int capacity;	 // termArray의 크기
	int terms;	 // 0이 아닌 항의 수
};

Polynomial 밑에 Term을 선언하면 굳이 전방 선언이 필요없지만 복습 할 겸 일부러 위에 넣었습니다. friend 로 선언하기 위해서는 Polynomial 이 밑에 선언되어 있다는 것을 전방 선언을 통해 컴파일러에게 알려줘야만 합니다.

위 코드를 통해 틀을 잡았으니 바로 구현에 대한 설명을 하겠습니다. 최종적으로 사용하는 Polynomial.h 파일은 아래와 같습니다. 이 때 다항식의 입출력은 << 와 >> 연산자 오버로딩으로 구현하고, 입력은 비주얼 스튜디어의 리소스 파일 .in 의 형태로 전달합니다.

// Polynomial.h
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
using namespace std;

class Polynomial; // 전방참조
class Term {
	friend class Polynomial;
	friend ostream& operator<<(ostream&, Polynomial&);
	friend istream& operator>>(istream&, Polynomial&);
private:
	float coef;     // 계수
	int exp;	// 지수
};
class Polynomial {
public:
	Polynomial(); // p(x) = 0 생성
	Polynomial operator+(Polynomial&); // 다항식의 합을 반환
	Polynomial operator*(Polynomial&); // 다항식의 곱을 반환
	void NewTerm(const float, const int);
	friend ostream& operator<<(ostream&, Polynomial&);
	friend istream& operator>>(istream&, Polynomial&);
private:
	Term* termArray;
	int capacity; // 1로 초기화
	int terms; // 저장된 항의 수로 0으로 초기화
};
#endif

구현 되어야 하는 부분은 먼저 입력을 받는 부분이 되어야 하겠죠. 단순한 형태로 맨 앞에 항의 개수, 그 이후는 float 계수 int 차수 가 띄어쓰기를 기준으로 받는 형태로 정의하겠습니다. 그 다음으로 출력 >> 은 짜다보니 코드가 되게 복잡해보이는데, 그냥 예외처리랑 이쁘게 통일성을 막 맞추려다 보니까 조금 복잡해졌습니다. 제가 만들려 했던 의도는 계수가 +1이나 -1인 경우에는 그냥 +와 -로 처리가 되는 대신, 만약 차수가 0이라면 +1이나 -1도 표시하도록, 그리고 맨 첫 항의 +는 표시하지 않도록 구현하고자 했습니다.

NewTerm 은 capacity가 꽉 찬 경우 2배로 늘린 이후에 새로운 항을 추가하는 기능이 들어갑니다. + 연산이 조금 복잡하고, * 연산이 상대적으로 간단합니다. 먼저 전체 코드를 보고 부분적으로 해설을 해보겠습니다.

// Polynomial.cpp
#include <iostream>
#include "Polynomial.h"
using namespace std;

istream& operator>> (istream& is, Polynomial& p) {
	// terms(항의 개수), (coefficoent, exponent)의 pair들을 읽어들인다.
	// 높은차수의 항부터 저장되었다고 가정
	int term_count, exp;
	float coef;
	is >> term_count;
	for (int i = 0; i < term_count; i++) {
		is >> coef >> exp;    // 계수와 지수 pair를 읽어들인다.
		p.NewTerm(coef, exp);
	}
	return is;
}


ostream& operator<< (ostream& os, Polynomial& p) {
	if (p.terms == 0) {
		os << "0";
		return os;
	}

	for (int i = 0; i < p.terms; i++) {
		// 차수 0이 아닌 경우
		if (p.termArray[i].exp != 0) {
			// 계수가 1인 경우
			if (p.termArray[i].coef == 1) {
				if (i == 0) os << "x^" << p.termArray[i].exp;
				else os << " +x^" << p.termArray[i].exp;
			}
			// 계수가 -1인 경우
			else if (p.termArray[i].coef == -1) {
				if (i == 0) os << "-x^" << p.termArray[i].exp;
				else os << " -x^" << p.termArray[i].exp;
			}
			// 양수이면 +(계수)x^(차수)의 형태로 출력
			else if (p.termArray[i].coef > 0) {
				if (i == 0) os << p.termArray[i].coef << "x^" << p.termArray[i].exp;
				else os << " +" << p.termArray[i].coef << "x^" << p.termArray[i].exp;
			}
			// 음수이면 (계수)x^(차수)의 형태로 출력
			else
			{
				if (i == 0) os << p.termArray[i].coef << "x^" << p.termArray[i].exp;
				else os << " " << p.termArray[i].coef << "x^" << p.termArray[i].exp;
			}
		}
		else {
			// 차수가 0인 경우
			if (p.termArray[i].coef > 0) os << " +" << p.termArray[i].coef;
			else os << " " << p.termArray[i].coef;
		}
	}
	cout << endl;
	return os;
}


Polynomial::Polynomial() :capacity(1), terms(0) {
	termArray = new Term[capacity];
}

void Polynomial::NewTerm(const float Coef, const int Exp)
{
	// 만약 term과 capacity가 같다면(더 저장할 공간이 없다면) termArray의 크기를 2배로 확장
	if (terms == capacity) {
		capacity *= 2;
		Term* temp = new Term[capacity];		  // 2배 크기의 term
		copy(termArray, termArray + terms, temp); // temp에 termArray의 내용 복사
		delete[] termArray;						  // 그전 메모리 반환
		termArray = temp;						  // term 이 새로운 termArray가 된다.
	}
	// 새로운 항을 추가
	termArray[terms].coef = Coef;
	termArray[terms].exp = Exp;
	terms++; // 항 개수 업데이트
}

Polynomial Polynomial::operator+(Polynomial& b)
{
	// a(*this) + b = c 를 구현
	Polynomial c;
	int aPos = 0, bPos = 0; // 현재 연산을 하는 포지션을 의미한다.

	// 차수가 큰 항부터 저장되어 있기 때문에 같으면 계수를 더하고 더 높은 차수가 나타나면 바로 c에 더한다.
	// a나 b중 하나의 다항식에 대한 연산이 끝나면 나머지 다항식에 남은 항들을 모두 c에 더한다.
	while ((aPos < terms) && (bPos < b.terms)) {

		if (termArray[aPos].exp == b.termArray[bPos].exp) { // 차수가 같은 경우 계수 덧셈
			float temp = termArray[aPos].coef + b.termArray[bPos].coef;
			if (temp != 0) {
				c.NewTerm(temp, termArray[aPos].exp); // 더한 결과를 추가. exp는 bPos여도 무방
			}
			aPos++;
			bPos++;
		}
		else if (termArray[aPos].exp < b.termArray[bPos].exp) {
			// aPos 위치의 차수보다 bPos 위치의 차수가 더 큰 경우 b의 bPos 위치 항을 c에 추가
			c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
			bPos++;
		}
		else {
			// aPos 위치의 차수가 bPos 위치의 차수보다 더 큰 경우 a(*this)의 aPos 위치 항을 c에 추가
			c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
			aPos++;
		}
	}

	// 다항식 a나 b에 남은 항이 있다면 모두 c에 더함
	for (; aPos < terms; aPos++) {
		c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
	}
	for (; bPos < b.terms; bPos++) {
		c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
	}

	return c;
}

Polynomial Polynomial::operator*(Polynomial& b)
{
	Polynomial c;
	for (int i = 0; i < terms; i++) {
		for (int j = 0; j < b.terms; j++) {
			float newCoef = termArray[i].coef * b.termArray[j].coef;
			int newExp = termArray[i].exp + b.termArray[j].exp;
			c.NewTerm(newCoef, newExp);
			// c = c + Polynomial(newCoef, newExp);
		}
	}
	return c;
}

위 코드가 Polynomial.h에 선언되었던 원형들을 전부 구현한 코드입니다. 입출력 연산자 오버로딩은 위에서 간단히 설명했으니 생략하고 함수 한 개씩 뜯어서 설명하겠습니다.

 

Polynomial::Polynomial() :capacity(1), terms(0) {
	termArray = new Term[capacity];
}

void Polynomial::NewTerm(const float Coef, const int Exp)
{
	// 만약 term과 capacity가 같다면(더 저장할 공간이 없다면) termArray의 크기를 2배로 확장
	if (terms == capacity) {
		capacity *= 2;
		Term* temp = new Term[capacity];	  // 2배 크기의 term
		copy(termArray, termArray + terms, temp); // temp에 termArray의 내용 복사
		delete[] termArray;			  // 그전 메모리 반환
		termArray = temp;			  // term 이 새로운 termArray가 된다.
	}
	// 새로운 항을 추가
	termArray[terms].coef = Coef;
	termArray[terms].exp = Exp;
	terms++; // 항 개수 업데이트
}

생성자와 NewTerm 코드입니다. 먼저 capacity는 termArray의 크기를 말합니다. terms가 저장하는 바는 저장되어 있는 항의 개수입니다. 맨 처음 생성을 하면 1개짜리 배열을 만들어놓고, 아직 terms 는 0인 것이죠.

 

그러면 이제 항을 한개 추가하면 capacity도 1이고 term도 1인 상태이죠. 이런 상황에서 또 Newterm을 호출하게 되면 배열이 꽉 찼기 때문에 배열을 확장해주는 작업이 정의되어있는 것입니다. 주석이 자세하니 이정도 설명하고 넘어가도록 하겠습니다.

 

Polynomial Polynomial::operator+(Polynomial& b)
{
	// a(*this) + b = c 를 구현
	Polynomial c;
	int aPos = 0, bPos = 0; // 현재 연산을 하는 포지션을 의미한다.

	// 차수가 큰 항부터 저장되어 있기 때문에 같으면 계수를 더하고 더 높은 차수가 나타나면 바로 c에 더한다.
	// a나 b중 하나의 다항식에 대한 연산이 끝나면 나머지 다항식에 남은 항들을 모두 c에 더한다.
	while ((aPos < terms) && (bPos < b.terms)) {

		if (termArray[aPos].exp == b.termArray[bPos].exp) { // 차수가 같은 경우 계수 덧셈
			float temp = termArray[aPos].coef + b.termArray[bPos].coef;
			if (temp != 0) {
				c.NewTerm(temp, termArray[aPos].exp); // 더한 결과를 추가. exp는 bPos여도 무방
			}
			aPos++;
			bPos++;
		}
		else if (termArray[aPos].exp < b.termArray[bPos].exp) {
			// aPos 위치의 차수보다 bPos 위치의 차수가 더 큰 경우 b의 bPos 위치 항을 c에 추가
			c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
			bPos++;
		}
		else {
			// aPos 위치의 차수가 bPos 위치의 차수보다 더 큰 경우 a(*this)의 aPos 위치 항을 c에 추가
			c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
			aPos++;
		}
	}

	// 다항식 a나 b에 남은 항이 있다면 모두 c에 더함
	for (; aPos < terms; aPos++) {
		c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
	}
	for (; bPos < b.terms; bPos++) {
		c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
	}

	return c;
}

다항식 덧셈이 좀 어렵습니다. 먼저 구조를 살펴보면 a+b=c를 계산하는 구조이고, 이 때 멤버함수로 선언이 되어 있기 때문에 a는 *this 가 됩니다. a 다항식이나 b 다항식 모두 높은 차수부터 저장이 되어 있을 겁니다. while 문을 통해 높은 차수부터 차례대로 쭉 훑는 것을 다른 말로 말하면 0부터 term 인덱스까지 termArray를 순회하는 것과 동일합니다.

 

이 때 같은 차수를 만나면 계수를 더하고 둘 중 하나에만 그 차수가 있다면 그대로 c에 더하는 방식입니다. 이 코드는 a와 b가 모두 높은 차수 순서대로 저장되어 있다는 가정하에 성립하는 코드입니다. 

 

a(x)=x7+3x3+1 이 있고 b(x)=x4−x3+x2+x+1 이 있다고 가정을 해봅시다. while 문이 돈다면 첫번째 조건문인 if (termArray[aPos].exp == b.termArray[bPos].exp) 는 당연히 통과될겁니다. 왜냐하면 좌변은 7이 되고 우변은 4가 되기 때문이죠. 첫 번째 while 내 반복에서는 else, 즉 a가 더 큰 상황에 대해서 걸리게 되어 c에는 x7이 추가가 되고, aPos만 1이 증가하게 됩니다.

 

그럼 현재 while이 1번 돌아간 상황에서 aPos = 1, bPos = 0 인 상태로 while 이 또 돌아가는 겁니다. 이번에는 termArray[aPos].exp=3 이고, b.termArray[bPos].exp = 4 이기 때문에 중간의 else if 문에 걸리고, c에 x4가 추가되고 bPos만 1 증가하게 됩니다.

 

그 이후에는 둘 다 차수가 3으로 같으므로 계수를 계산한 다음에 c에 추가되겠죠? 이런 식으로 돌다가 a가 먼저 다 끝나면 남은 b에 있는 걸 모두 c에 더한다고 생각하시면 되겠습니다.

 

Polynomial Polynomial::operator*(Polynomial& b)
{
	Polynomial c;
	for (int i = 0; i < terms; i++) {
		for (int j = 0; j < b.terms; j++) {
			float newCoef = termArray[i].coef * b.termArray[j].coef;
			int newExp = termArray[i].exp + b.termArray[j].exp;
			c.NewTerm(newCoef, newExp);
			// c = c + Polynomial(newCoef, newExp);
		}
	}
	return c;
}

곱셈은 2차원 배열 돌리는 느낌과 비슷합니다. 차수와 계수 모두 각각 곱해서 새로 추가해주시면 되고, 이 때 주석 처리해놓은 부분은 만약 + 연산자 오버로딩을 위처럼 구현해놓았다면 아래 표현처럼 c.NewTerm 대신 사용해 곱셈을 구현해도 되기 때문에 추가해봤습니다. 

 

 

출력 결과에 사용한 main.cpp 코드는 아래와 같고, 입력은 스크린샷에 나와 있습니다.

// main.cpp
#include <iostream>
using namespace std;
#include "Polynomial.h"

int main() {
	Polynomial p1, p2, p3, p4, p5, p6;
	cin >> p1 >> p2;
	p3 = p1 + p2;
	cout << endl;
	cout << p1 << p2 << p3 << endl;

	cin >> p4 >> p5;
	p6 = p4 * p5;
	cout << endl;
	cout << p4 << p5 << p6;
}

 

사실 배열로 다항식을 저장하는 건 되게 비효율적인 자료구조이죠. 그래도 이렇게 직접 구현해보면 생각만큼 아주 간단하진 않고 이를 통해 C++ 기초 코딩에 대해 복습도 할겸 한번쯤은 다들 짜보시는 걸 권장드립니다. 감사합니다.

 

 

Reference : Ellis, Horowitz. C++ 자료구조론(2판). 대한민국: 인피니티북스, 2007.

저작자표시 비영리 동일조건

'C++ > C++ 자료구조' 카테고리의 다른 글

BFS 를 사용해 미로의 최단 경로 출력하기  (1) 2023.10.15
Container class - Bag, Stack, Queue C++ pesudo code  (1) 2023.10.15
배열을 이용한 희소 행렬 표현 (Sparse matrices representations using Array)  (1) 2023.10.15
[C++] STL 정리 ( pair, vector, stack, queue, deque, map, set, algorithm )  (0) 2023.05.05

'C++/C++ 자료구조'의 다른글

  • 현재글배열을 이용한 다항식 ADT의 표현 (Polynomial ADT using Array) - 다항식의 덧셈과 곱셈

관련글

티스토리툴바