[자료구조] 다항식(Polynomial)과 다항식 연산자(Operation of Polynomial)

다항식이란?

여러 항들의 합으로 이루어진 식
ex) A(x) = 3x^20 + 2x^5 + 4

항은 변수(variable), 계수(coefficient), 지수(exponent)로 이루어져 있다.

Polynomial ADT 예시(Java)

먼저 단항에 관한 정보를 담는 클래스 Poly를 작성해줍니다.

class Poly{
	double coef;	// 계수
	int exp;	// 지수
	
	public Poly() {
		this.coef = 0;
		this.exp = 0;
	}

	public Poly(double coef, int exp) {
		this.coef = coef;
		this.exp = exp;
	}
}

이때 멤버변수 coef는 int로 선언해도 무관합니다. Poly를 이용해 x^4 + 10x^3 + 3x^2 + 1이라는 다항식을 만들면 다음과 같습니다.

Poly[] poly = { new Poly(1, 4), new Poly(10, 3), new Poly(3, 2), new Poly() };

이제 다항식 연산자들을 클래스 Polynomial의 메소드로 구현해보겠습니다.

1. 다항식을 0으로 만드는 연산자 setZero

public static void setZero(Poly[] poly) {
	for(int i=0; i<poly.length; i++) 
		poly[i].coef = 0;
}

setZero는 모든 항의 계수를 0으로 만들어 결론적으로 다항식을 0으로 만들어줍니다. 실행 결과는 2번을 수행한 후 같이 확인하도록 하겠습니다.

2. 다항식이 0인지 판별하는 연산자 isZero

public static boolean isZero(Poly[] poly) {
	for(int i=0; i<poly.length; i++) 
		if(poly[i].coef != 0)
			return false;
            
	return true;
}

isZero는 다항식이 0이면 true, 0이 아니면 false를 반환하는 함수입니다. 모든 항을 검사해서 계수가 0이 아닌 항이 있으면 false를 반환합니다. isZero와 setZero를 메인메소드에서 실행해보면 결과는 다음과 같습니다.

public static void main(String[] args) {
	// poly = 2x^100 + 1
	Poly[] poly = { new Poly(2, 100), new Poly(1, 0) };	

	printPoly(poly);
	setZero(poly);
	printPoly(poly);
}

3. 해당 항의 지수를 받아 계수를 반환하는 연산자 getCoef

public static double getCoef(Poly[] poly, int exp) {
	for(int i=0; i<poly.length; i++) {
		if(poly[i].exp == exp) 
			return poly[i].coef;
	}
	return 0;
}

getCoef는 지수 값을 파라미터로 받아 해당 항이 있으면 계수를 반환하고, 없으면 0을 반환합니다. 실행결과는 다음과 같습니다.

public static void main(String[] args) {
	// poly = x^4 + 10x^3 + 3x^2 + 1
	Poly[] poly = { new Poly(1, 4), new Poly(10, 3), new Poly(3, 2), new Poly(1, 0) };	
	System.out.println(getCoef(poly, 3));
}

4. 다항식의 최고차항을 반환하는 연산자 getLeadExp

public static int getLeadExp(Poly[] poly) {
	int maxExp = 0;
	for(int i=0; i<poly.length; i++) {
		if(poly[i].exp > maxExp) 
			maxExp = poly[i].exp;
	}
	return maxExp;
}

반복문을 돌면서 지수의 최대값을 maxExp에 저장하고 최종적으로 이를 반환합니다.

public static void main(String[] args) {
	// poly = 2x^10 + 3x^5 + 1
	Poly[] poly = { new Poly(3, 5), new Poly(2, 10), new Poly(1, 0) };	

	System.out.println(getLeadExp(poly));
}

5. 항을 추가해주는 연산자 attach

public static Poly[] attach(Poly[] poly, double coef, int exp) {
	final int NEW_POLY_SIZE = poly.length + 1;
	Poly[] newPoly = new Poly[NEW_POLY_SIZE];
	int position = 0; // 항을 추가할 위치

	if(exp == 0) {
		// 지수가 0인 상수일 경우 맨끝에 추가
		position = NEW_POLY_SIZE - 1;
		newPoly[position] = new Poly(coef, exp);
	} else if(exp > getLeadExp(poly)) {
		// 최고차항보다 클 경우
		newPoly[position] = new Poly(coef, exp);
	}else {
		for(int i=1; i<poly.length; i++) {
			// 삽입 위치 찾기
			if(exp < poly[i-1].exp && exp > poly[i].exp) 
				position = i;
		}
		for(int i=0; i<NEW_POLY_SIZE; i++) {
			if(i < position)
				newPoly[i] = poly[i];
			else if(i == position)
				newPoly[position] = new Poly(coef, exp);
			else
				newPoly[i] = poly[i-1];
		}
	}
		
	return newPoly;
}

새로운 항을 추가하는 attach 함수를 작성했습니다. 이때, 다항식은 내림차순으로 정렬되어 있음을 전제합니다. 항을 추가하는 방법은 크게 세가지입니다. 추가하고자하는 항이 상수인 경우, 최고차항보다 클 경우, 중간에 들어가야할 항인 경우입니다. 앞의 두가지 경우는 쉽게 구현할 수 있는데, 마지막 케이스는 삽입 위치를 찾아준 후 위치에 따라서 다르게 복사를 해주어야 배열의 중간에 요소가 삽입될 수 있어야 합니다.
ArrayList를 사용하는 방법도 있습니다.

6. 항을 제거하는 연산자 remove

public static Poly[] remove(Poly[] poly, int exp) {
	final int NEW_POLY_SIZE = poly.length - 1;
	Poly[] newPoly = new Poly[NEW_POLY_SIZE];
	int position = 0;

	for(int i=0; i<poly.length; i++)
		if(exp == poly[i].exp)
			position = i;
		
	for(int i=0; i<NEW_POLY_SIZE; i++) {
		if(i < position)
			newPoly[i] = poly[i];
		else if(i >= position)
			newPoly[i] = poly[i+1];
	}
		
	return newPoly;
}

remove도 attach와 유사한데, 제거할 위치를 찾아준 후 해당 위치 전후로 복사를 다르게 수행해주면 배열에 비어있는 칸 없이 제거가 가능합니다. remove와 attach를 같이 실행해보면 다음과 같습니다.

public static void main(String[] args) {
	// poly = 2x^10 + 3x^5 + 1
	Poly[] poly = { new Poly(2, 10), new Poly(3, 5), new Poly(1, 0) };	

	poly = attach(poly, 4.2, 4);	// 4.2x^4 항 추가
	printPoly(poly);
	poly = remove(poly, 4); 	// 4.2x^4 항 제거
	printPoly(poly);
}

7. 단항과의 곱셈을 실시하는 연산자 monoMultiply

public static Poly[] monoMultiply(Poly[] poly, double coef, int exp) {
	final int NEW_POLY_SIZE = poly.length;
	Poly[] newPoly = new Poly[NEW_POLY_SIZE];

	for(int i=0; i<NEW_POLY_SIZE; i++) {
		newPoly[i] = new Poly(poly[i].coef * coef, poly[i].exp + exp);
				
	}
		
	return newPoly;
}

monoMultiply는 coef는 곱하고 exp는 더해서 newPoly에 저장합니다. 아래는 실행결과입니다.

public static void main(String[] args) {
	// poly = 2x^10 + 3x^5 + 1
	Poly[] poly = { new Poly(2, 10), new Poly(3, 5), new Poly(1, 0) };	

	poly = monoMultiply(poly, 2.5, 2);	// 2.5x^2 항 곱하기
	printPoly(poly);
}

8. 두 다항식을 더해주는 연산자 add

public static Poly[] add(Poly[] poly1, Poly[] poly2) {
	final int NEW_POLY_SIZE = poly1.length + poly2.length;
	Poly[] newPoly = new Poly[NEW_POLY_SIZE];

	int poly1_start = 0, poly1_end = poly1.length - 1;
	int poly2_start = 0, poly2_end = poly2.length - 1;
	int position = 0;
		
	while(poly1_start <= poly1_end && poly2_start <= poly2_end) {
		// 비교할 항이 남아 있는 동안 반복
		if(poly1[poly1_start].exp < poly2[poly2_start].exp) {
			// poly2의 계수가 더 클 경우 poly2의 항이 먼저 나와야함
			newPoly[position++] = new Poly(poly2[poly2_start].coef, poly2[poly2_start].exp);
			poly2_start++;
		}
		if(poly1[poly1_start].exp > poly2[poly2_start].exp) {
			newPoly[position++] = new Poly(poly1[poly1_start].coef, poly1[poly1_start].exp);
			poly1_start++;
		}
		if(poly1[poly1_start].exp == poly2[poly2_start].exp){
			// 두 항의 지수가 같은 경우
			double coef = poly1[poly1_start].coef + poly2[poly2_start].coef;
			if(coef != 0)
				// 계수의 합이 0인 경우 포함시키지 않음
				newPoly[position++] = new Poly(coef, poly1[poly1_start].exp);
			poly1_start++; poly2_start++;
		}
	}
	// 남아있는 항 추가
	for(; poly1_start<=poly1_end; poly1_start++) {
		newPoly[position++] = new Poly(poly1[poly1_start].coef, poly1[poly1_start].exp);
	}
	for(; poly2_start<=poly2_end; poly2_start++) {
		newPoly[position++] = new Poly(poly1[poly2_start].coef, poly1[poly2_start].exp);
	}
		
	return newPoly;
}

add는 다소 복잡하긴 하지만, 원리만 잘 알면 이해하기 쉽습니다. add는 두 다항식의 인덱스 값을 이용해서 덧셈을 수행하고 있는데요, 그림을 보면 보다 이해가 쉽습니다.

위와 같이 다항식 poly1, poly2가 있고 두 다항식을 더한 결과인 poly3가 있을 때, 인덱스가 poly1_start부터 poly1_end까지, poly2_start부터 poly2_end까지 증가하면서 항의 지수(exp) 값을 비교합니다. 비교 결과 지수가 더 큰 항이 먼저 와야하므로 poly3의 position에 저장됩니다. 만약 같다면 두 항의 계수를 더한 후 저장하면 됩니다.

같은 방식으로 코드를 작성하면, start 인덱스들이 end 인덱스들보다 작을 때 동안 앞에서 설명한 비교와 저장을 반복합니다. 이때 저장한 쪽의 인덱스 값을 증가시켜줘야 하며, 같을 경우에는 계수가 0이 되는지 확인한 후 저장해야 하고 두 인덱스 모두 증가시켜줘야 합니다. 그런 다음에는 아직 저장되지 않은 나머지 값들까지 모두 저장하는 반복문을 작성하면 됩니다.

실행 예시는 다음과 같습니다.

public static void main(String[] args) {
	// poly = 2x^10 + 3.4x^8 + 3x^2 + 1
	Poly[] poly1 = { new Poly(2, 10), new Poly(3.4, 8), new Poly(3, 2), new Poly(1, 0) };	
	// poly = 3x^8 + 5x^5 - 3x^2 + 12.5
	Poly[] poly2 = { new Poly(3, 8), new Poly(5, 5), new Poly(-3, 2), new Poly(12.5, 0) };
		
	Poly[] poly3 = add(poly1, poly2);
	printPoly(poly3);
}