[Data Structure] CHAP 3. Polynomials (다항식) - C언어 ver.

지난 챕터 Arrays에 이어 이번 챕터에서는 Polynomials에 대한 내용을 기록하려 한다. 사실 앞의 내용들은 전부 익숙한 내용이었는데, polynomial은 처음 듣는 키워드라 걱정이 조금 됐었다. 그런데 막상 배워보니까 크게 어려운 개념은 아니라는 점!! 어쨋든 이번 챕터에서는
✅ polynomial의 개념알기
✅ polynomial을 ADT로 표현하기, ADT를 참고해 구현하기
를 해보려고 한다.

---

1. Polynomial이란?

polynomial은 쉽게 간단히 말하면 다항식이다. 다항식을 이차원 배열의 형태로 표현하며, coef와 exp를 써준다. 이때, coef는 항의 계수이며 exp는 차수를 의미한다. 즉, Polynomial A = [[2,1000],[1,0]] 이라면 2Χ^1000 + 1 라는 다항식을 나타내게 된다.

---

2. Polynomial 구현하기

polynomial을 구현하기 전에 ADT를 이용해 설계를 해보려고 한다. 제곱을 쓰기에 제한이 있어 사진을 첨부하기로 한다.

polynomial의 ADT

사용할 함수가 생각보다 많았다! 이를 이용하여 두 다항식의 합을 구현해보려고 한다.

2-1. initial version of padd funcion

두 다항식의 합을 구현해보자. d = a + b 이며 a,b,d 모두 다항식이다.

d = Zero()
while (!IsZero(a) && !IsZero(b)) do {
	switch COMPARE(LeadExp(a), LeadExp(b)) {
    	case -1:
        	d = Attach(d, Coef(b,LeadExp(b)), LeadExp(b));
            b = Remove(b,LeadExp(b));
            break;
        case 0:
        	sum = Coef(a,LeadExp(a)) + Coef(b,LeadExp(b));
            if (sum) {
				Attach(d,sum,LeadExp(a));
 
            }
            a = Remove(a,LeadExp(a));
            b = Remove(b,LeadExp(b));
            break;
        case 1:
        	d = Attach(d,Coef(a,LeadExp(a)),LeadExp(a));
            a = Remove(a,LeadExp(a));
     }
}
insert any remaining terms of a or b into d

이런식으로 구현할 수 있었다! case -1은 a<b인 경우를 의미하며 case 1은 a>b, case 0은 a=b인 경우에 작동하는 것이다.