문제 소개
두 개의 다항식이 주어졌을 때, 이 둘의 합을 구해야 한다고 가정해 보겠습니다. 다항식은 연결 리스트(Linked List) 형태로 표현하며, 다항식의 각 항은 하나의 노드로 나타냅니다. 각 노드는 다음 세 가지 정보를 포함합니다.
- 계수(coefficient): 항의 계수 값
- 차수(power): 변수 x의 지수
- 포인터(next): 다음 노드를 가리키는 참조
즉, 최종적으로 반환해야 할 것은 두 다항식의 합을 담고 있는 세 번째 연결 리스트입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
1x^1 + 1x^2 = 0 과 2x^1 + 3x^0 = 0
그렇다면 출력은 다음과 같습니다.
3x^1 + 1x^2 + 3x^0 = 0
알고리즘 접근 방법
이 문제는 정렬된 두 리스트를 병합(merge)하는 방식과 매우 유사하게 해결할 수 있습니다. 두 다항식의 노드를 차수 기준으로 비교하면서 앞에서부터 순회하고, 차수가 같은 항끼리 만나면 계수를 서로 더해 주면 됩니다. 구체적인 단계는 다음과 같습니다.
- 결과 리스트의 시작점 역할을 할 더미(dummy) 노드를 생성합니다.
- poly1과 poly2가 모두 비어 있지 않은 동안 다음 과정을 반복합니다.
- poly1의 차수 > poly2의 차수인 경우: node.next에 poly1을 연결하고, node를 poly1로 이동한 뒤, poly1도 다음 노드로 이동시킵니다.
- poly1의 차수 < poly2의 차수인 경우: node.next에 poly2를 연결하고, node를 poly2로 이동한 뒤, poly2도 다음 노드로 이동시킵니다.
- 두 차수가 같은 경우: 양쪽 계수를 더해 coef에 저장합니다. coef가 0이 아니라면 새 노드를 만들어 결과에 추가하고, 0이라면 해당 항은 생략합니다(소거). 이후 poly1과 poly2를 모두 다음 노드로 이동시킵니다.
- 반복이 종료되면 아직 처리되지 않은 남은 노드(poly1 또는 poly2)를 결과 리스트 뒤에 그대로 이어 붙입니다.
- 더미 노드의 다음 노드(dummy.next)를 반환하면 완성된 합 다항식을 얻을 수 있습니다.
Python 구현 예제
위 알고리즘을 실제 코드로 구현하면 다음과 같습니다.
class polynomial:
def __init__(self, coeff=0, pow=0, nxt=None):
self.coefficient = coeff
self.power = pow
self.next = nxt
def create_poly(expression):
head = None
for element in expression:
if head is None:
head = polynomial(element[0], element[1])
else:
temp = head
while temp.next != None:
temp = temp.next
temp.next = polynomial(element[0], element[1])
return head
def show_poly(head):
temp = head
while temp.next != None:
print(str(temp.coefficient) + 'x^' + str(temp.power), end=' + ')
temp = temp.next
if temp.next == None:
print(str(temp.coefficient) + 'x^' + str(temp.power), end=' = 0')
def solve(poly1, poly2):
dummy = node = polynomial()
while poly1 and poly2:
if poly1.power > poly2.power:
node.next = node = poly1
poly1 = poly1.next
elif poly1.power < poly2.power:
node.next = node = poly2
poly2 = poly2.next
else:
coef = poly1.coefficient + poly2.coefficient
if coef:
node.next = node = polynomial(coef, poly1.power)
poly1 = poly1.next
poly2 = poly2.next
node.next = poly1 or poly2
return dummy.next
poly1 = create_poly([[1, 1], [1, 2]])
poly2 = create_poly([[2, 1], [3, 0]])
poly3 = solve(poly1, poly2)
show_poly(poly3)
실행 입력
poly1 = create_poly([[1, 1], [1, 2]]) poly2 = create_poly([[2, 1], [3, 0]])
실행 결과
3x^1 + 1x^2 + 3x^0 = 0
코드 구성 요소 살펴보기
- polynomial 클래스: 계수, 차수, next 포인터를 저장하는 다항식 노드를 정의합니다.
- create_poly 함수: [[계수, 차수], ...] 형태의 리스트를 받아 연결 리스트로 변환합니다.
- show_poly 함수: 다항식을 사람이 읽기 쉬운 "3x^1 + 1x^2" 형태의 문자열로 출력합니다.
- solve 함수: 실제 덧셈 연산을 수행하는 핵심 로직입니다.
시간 및 공간 복잡도
- 시간 복잡도: O(m + n) — m과 n은 각각 두 다항식의 항 개수입니다. 두 리스트를 한 번씩만 순회하면 되기 때문입니다.
- 공간 복잡도: O(max(m, n)) — 결과 리스트는 두 다항식 중 더 많은 항을 가진 쪽과 같거나 작은 크기를 가집니다.
마무리
연결 리스트로 표현된 다항식 덧셈은 본질적으로 두 정렬 리스트를 병합하는 문제와 같습니다. 차수를 비교하며 노드를 순서대로 연결하고, 차수가 같은 경우 계수를 더해 주면 됩니다. 특히 계수의 합이 0이 되는 항은 자동으로 제외되므로, 희소 다항식(sparse polynomial)을 처리할 때도 유용하게 활용할 수 있는 패턴입니다.