4. 다항식 덧셈은 남은 항까지 합쳐야 한다
해설글
작성 · 4분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
다항식을 노드의 줄로 바꾸는 문제
다항식 $3x^4+2$와 $-3x^4+5x-2$를 더하면 같은 지수끼리 계수를 합쳐 $5x$를 얻어야 한다. 항은 계수와 지수의 쌍이며, (3,4)는 $3x^4$를 뜻한다. 각 항을 노드로 저장하면 항의 개수가 적은 다항식에 불필요한 0 계수를 저장하지 않아도 된다.
두 입력 리스트가 지수 내림차순이라면 맨 앞 노드가 각 다항식에서 아직 처리하지 않은 가장 큰 지수다. 각 리스트의 현재 노드를 가리키는 두 순회 포인터를 두고 지수를 비교하면 된다. 포인터가 다음 노드로만 이동하므로 이미 처리한 항으로 돌아가지 않는다.
입력은 정렬된 두 항 리스트이고, 원하는 결과는 같은 지수의 항을 하나로 합친 정렬 리스트다. 두 리스트의 길이가 다를 수 있으므로 한쪽 포인터가 끝에 도착했을 때 다른 쪽에 남은 항도 반드시 복사해야 한다.
마지막 노드가 빠질 수 있다는 기록
디버깅 기법 노트에는 두 연결리스트를 연산할 때의 경고가 남아 있다.
반복의 조건을 잘 봐야한다. 마지막 노드나 첫번째 노드가 연산에서 제외될 수 있다!
다항식 덧셈 코드를 보면 이 경고가 필요한 지점이 선명하다. 각 항을 (계수, 지수) 노드로 만들고 지수가 큰 순서로 연결하면 두 다항식을 앞에서부터 비교할 수 있다.
A = 3x⁴ + 2 → (3,4) → (2,0)
B = -3x⁴ + 5x - 2 → (-3,4) → (5,1) → (-2,0)
두 입력은 지수 내림차순이다. 이 정렬이 두 포인터 알고리즘의 전제다. 예를 들어 B를 (-3,4) → (-2,0) → (5,1)처럼 넣으면 뒤늦게 더 큰 지수가 나타나 현재 노드끼리의 비교만으로 정렬된 합을 만들 수 없다.
두 포인터가 움직이는 세 경우
저장소의 다항식 덧셈은 curr1과 curr2가 가리키는 지수를 비교한다.
| 비교 | 결과에 넣는 항 | 움직이는 포인터 |
|---|---|---|
exp1 > exp2 |
A의 현재 항 | curr1 |
exp1 < exp2 |
B의 현재 항 | curr2 |
exp1 == exp2 |
계수의 합 | 둘 다 |
같은 지수의 계수를 더한 값이 0이면 그 항은 결과에 넣지 않는다. 여기까지는 두 리스트에 비교할 항이 모두 있을 때만 가능하다.
while (curr1 != tail1 && curr2 != tail2) {
/* 지수를 비교하고 한쪽 또는 양쪽 포인터를 이동 */
}
핵심 while은 둘 중 하나만 끝나도 멈춘다. 이때 다른 리스트에 항이 남아 있을 수 있다. 따라서 뒤의 두 반복문은 부가 처리가 아니라 알고리즘의 일부다.
while (curr1 != tail1) { append(curr1); curr1 = curr1->next; }
while (curr2 != tail2) { append(curr2); curr2 = curr2->next; }
이 부분이 없으면 공통 구간까지만 계산하고 긴 다항식의 꼬리를 잃는다. 노트의 “마지막 노드가 제외될 수 있다”는 말이 바로 이 종료 조건과 연결된다.
끝을 찾는 비용도 함께 보기
원본의 appendTerm은 항을 하나 넣을 때마다 Head에서 출발해 마지막 노드를 찾는다. 결과 항이 k개라면 탐색 길이가 0, 1, 2, …로 늘어 전체 작성 비용이 $O(k^2)$가 된다. 두 입력을 한 번씩 훑는 merge 자체는 $O(n+m)$인데, append 구현이 장점을 가린다.
이번에 만든 tail 포인터 기반 검증 코드는 결과의 마지막 노드를 직접 들고 다닌다.
tail의 자료형은 Node *이며 “현재 마지막 노드가 어디인가”를 저장하는 포인터 변수다. append가 새 노드를 붙인 뒤 호출자가 가진 tail 자체를 새 마지막 노드로 바꾸려면 그 포인터 변수의 주소를 받아야 한다. 그래서 매개변수형이 Node **tail, 즉 노드 포인터를 가리키는 포인터가 된다. *tail은 호출자의 마지막 노드 포인터이고, (*tail)->next는 그 마지막 노드의 다음 링크다.
static int append(Node **tail, int coef, int exp) {
if (coef == 0)
return 1;
(*tail)->next = malloc(sizeof(Node));
if (!(*tail)->next)
return 0;
*tail = (*tail)->next;
**tail = (Node){coef, exp, NULL};
return 1;
}
호출자는 0을 받으면 이미 만든 결과 노드를 해제하고 덧셈을 중단한다.
정렬된 3x⁴ + 2와 -3x⁴ + 5x - 2를 넣어 다시 실행했다. $x^4$와 상수항은 계수가 0이 되어 사라지고, 한쪽에 남은 5x만 결과에 들어갔다.
5x^1
이 실행은 이번 글을 위해 새로 만든 검증이다. 결과가 정확히 (5,1) 노드 하나이고 다음 노드가 NULL인지 assert로도 검사했다. 과거에 같은 입력으로 오류를 재현했다고 해석하지 않는다.
더미 노드를 계산에서 제외하기
노트에는 “Head 등의 더미노드를 연산하지 않게 조심해야 한다”는 문장도 있다. 원본 구현이 Head1->next, Head2->next에서 시작하고 Tail에 닿기 전에 멈추는 이유다. 더미 노드는 연결을 편하게 하지만 계수와 지수를 가진 실제 항은 아니다.
경계 입력은 다음처럼 정리할 수 있다.
- 한쪽이 빈 다항식이면 다른 쪽의 모든 항을 복사한다.
- 같은 지수의 합이 0이면 결과 노드를 만들지 않는다.
- 두 리스트가 동시에 끝나지 않아도 남은 항 반복을 계속한다.
- 결과의 tail을 직접 갱신해 append를 상수 시간으로 만든다.
- 동적으로 만든 결과 노드는 출력 뒤 모두 해제한다.
한 리스트 안의 연결을 지키는 문제에서 두 리스트의 현재 위치와 결과 리스트의 끝을 동시에 지키는 문제로 범위가 넓어졌다. 반복문 하나가 끝났다는 사실은 계산이 끝났다는 뜻이 아니었다. 어느 포인터가 왜 끝났고, 다른 포인터에는 무엇이 남았는지를 확인해야 했다.