본격적인 구현에 앞서, 이해에 필요한 기본 개념부터 간단히 짚고 넘어가겠습니다.
기본 개념
연결 리스트(Linked List)는 각 요소를 리스트의 노드(node)라는 객체 형태로 저장하는 자료구조입니다. 모든 노드는 실제 데이터를 담는 부분과 다음 노드를 가리키는 링크, 두 부분으로 구성됩니다.
다항식(Polynomial)은 변수와 계수로 이루어진 수학식입니다. 예를 들어 x2 − 4x + 7과 같은 식이 여기에 해당합니다.
다항식 연결 리스트에서는 다항식의 계수(coeff)와 지수(exponent)가 리스트 노드의 데이터로 저장됩니다.
연결 리스트로 표현된 두 다항식을 더하려면 같은 차수(지수)를 가진 항의 계수끼리 서로 더해야 합니다. 이때 각 노드는 계수(coefficient), 지수(power), 다음 노드를 가리키는 링크 세 가지 멤버를 가집니다.
다항식을 저장하는 연결 리스트는 다음과 같은 형태입니다.
다항식 : 4x7 + 12x2 + 45
두 다항식을 더할 때는 양쪽 노드의 지수 값을 비교합니다. 지수가 같으면 계수를 더하고, 지수가 다르면 더 큰 지수의 항을 그대로 결과에 옮깁니다.
예시
입력 : p1 = 13x8 + 7x5 + 32x2 + 54 p2 = 3x12 + 17x5 + 3x3 + 98 출력 : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
설명 − 각 차수별로 지수가 같은 항을 찾아 계수를 더합니다(예: 7x5 + 17x5 = 24x5). 상수항 역시 지수가 0인 항으로 취급하여 54 + 98 = 152처럼 더한 뒤, 최종 다항식을 반환합니다.
알고리즘
입력 − 연결 리스트로 표현된 다항식 p1과 p2
Step 1: 연결 리스트의 모든 노드를 순회하며 Step 2~3을 반복한다. Step 2: 한쪽 노드의 지수가 더 크면 해당 노드를 결과 노드에 복사하고 다음 노드로 이동한다. Step 3: 두 노드의 지수가 같으면 계수를 더한 값과 지수를 함께 결과 노드에 복사한다. Step 4: 최종 결과 다항식을 출력한다.
두 리스트를 한 번씩만 순회하므로, 이 알고리즘의 시간 복잡도는 두 다항식의 항 수를 m, n이라 할 때 O(m+n)입니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
struct Node{
int coeff;
int pow;
struct Node *next;
};
void create_node(int x, int y, struct Node **temp){
struct Node *r, *z;
z = *temp;
if(z == NULL){
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
} else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
void polyadd(struct Node *p1, struct Node *p2, struct Node *result){
while(p1->next && p2->next){
if(p1->pow > p2->pow){
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
}
else if(p1->pow < p2->pow){
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
} else {
result->pow = p1->pow;
result->coeff = p1->coeff+p2->coeff;
p1 = p1->next;
p2 = p2->next;
}
result->next = (struct Node *)malloc(sizeof(struct Node));
result = result->next;
result->next = NULL;
}
while(p1->next || p2->next){
if(p1->next){
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
}
if(p2->next){
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
}
result->next = (struct Node *)malloc(sizeof(struct Node));
result = result->next;
result->next = NULL;
}
}
void printpoly(struct Node *node){
while(node->next != NULL){
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if(node->next != NULL)
printf(" + ");
}
}
int main(){
struct Node *p1 = NULL, *p2 = NULL, *result = NULL;
create_node(41,7,&p1);
create_node(12,5,&p1);
create_node(65,0,&p1);
create_node(21,5,&p2);
create_node(15,2,&p2);
printf("polynomial 1: ");
printpoly(p1);
printf("\npolynomial 2: ");
printpoly(p2);
result = (struct Node *)malloc(sizeof(struct Node));
polyadd(p1, p2, result);
printf("\npolynomial after adding p1 and p2 : ");
printpoly(result);
return 0;
}
실행 결과
polynomial 1: 41x^7 + 12x^5 + 65x^0 polynomial 2: 21x^5 + 15x^2 polynomial after adding p1 and p2 : 41x^7 + 33x^5 + 15x^2 + 65x^0
실행 결과를 보면 지수가 5로 같은 두 항(12x5와 21x5)의 계수가 더해져 33x5가 되었고, 나머지 항들은 지수 순서대로 그대로 결과에 포함된 것을 확인할 수 있습니다.