다항식의 계수 배열·덧셈·곱셈

수학식을 컴퓨터가 계산하려면 항들을 어떤 순서로 저장할지 약속해야 합니다. 목표는 다항식의 차수와 목록 인덱스를 연결하고 덧셈과 곱셈의 차수 처리를 구분하는 것입니다. 리스트·덧셈·곱셈을 준비하면 됩니다.

개념과 약속

다항식은 계수와 x의 음이 아닌 정수 거듭제곱 항들의 합입니다. 3 + 2x + 5x²에서 3,2,5는 계수, 0,1,2는 각 항의 차수입니다. 이 본문은 낮은 차수부터 배열 [3,2,5]에 저장합니다. x항이 없는 1+4x²는 [1,0,4]입니다. 빠진 칸을 지우면 뒤 항의 차수가 바뀝니다.

두 다항식 덧셈은 같은 인덱스 계수끼리 더합니다. 짧은 쪽에 없는 높은 차수의 계수는 0으로 봅니다. 결과 뒤쪽의 0은 최고차수를 불필요하게 늘리므로 제거하되 영다항식은 [0]으로 정규화합니다. 빈 배열도 입력의 영다항식으로 허용합니다. 아주 높은 차수 중 몇 항만 있으면 (차수,계수) 목록이나 딕셔너리의 희소 표현을 고려할 수 있지만 여기서는 조밀 배열을 구현합니다.

곱셈은 첫 다항식의 각 항을 둘째의 모든 항과 곱한 뒤 같은 차수로 모읍니다. a*xⁱ와 b*xʲ의 곱은 (a*b)*x⁽ⁱ⁺ʲ⁾라서 결과 인덱스 i+j에 계수 곱을 누적합니다. 길이 m과 n의 배열에는 최대 인덱스 m+n-2가 생겨 결과 칸 m+n-1개를 준비합니다. 이 연산을 계수 배열의 합성곱이라고도 부릅니다.

손으로 상태 추적하기

결과 [4,2,0,4]는 4+2x+4x³입니다. 가운데 0은 유지합니다.

곱셈 (1+2x)*(3+4x)의 상태는 다음과 같습니다.

1차 계수에는 서로 다른 두 곱이 기여하므로 덮어쓰지 않고 더합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def polynomial_add(first, second):
    result = [0] * max(len(first), len(second), 1)
    for i, coefficient in enumerate(first):
        result[i] += coefficient
    for i, coefficient in enumerate(second):
        result[i] += coefficient
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result


def polynomial_multiply(first, second):
    if not first or not second:
        return [0]
    result = [0] * (len(first) + len(second) - 1)
    for i, a in enumerate(first):
        for j, b in enumerate(second):
            result[i + j] += a * b
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result


print(polynomial_add([3, 2, 5], [1, 0, -5, 4]))
print(polynomial_add([1, 2], [-1, -2]))
print(polynomial_add([], []))
print(polynomial_multiply([1, 2], [3, 4]))
print(polynomial_multiply([], [1, 2]))

실행 결과:

[4, 2, 0, 4]
[0]
[0]
[3, 10, 8]
[0]

왜 맞고 언제 끝나는가

덧셈에서 각 인덱스 i의 결과는 같은 차수의 두 계수의 합입니다. 곱셈은 분배법칙으로 생기는 모든 항 쌍을 정확히 한 번 처리하고, 차수 i+j별로 모으므로 다항식 곱과 같습니다. 배열 끝의 0을 제거해도 식의 값은 변하지 않고 내부 0을 보존해 나머지 차수는 유지합니다. 유한한 입력 칸과 항 쌍을 처리하고 결과 길이가 줄어드는 정규화 반복이 끝납니다.

비용과 적용 범위

입력 계수 수 m,n에서 덧셈 시간 O(m+n), 결과 공간 O(max(m,n))입니다. 일반적인 두 반복 곱셈은 O(mn) 시간, O(m+n) 결과 공간입니다. 차수 100만인 단항식 x¹⁰⁰⁰⁰⁰⁰은 조밀 표현이 대부분 0이라 낭비가 큽니다. 계수의 큰 정수 연산 또는 실수 반올림은 단순 칸 수 분석 외의 문제입니다.

스스로 풀어 보기

1. 2x³+1을 이 표현으로 쓰고 -2x³+3x와 더하세요.
2. [4,2,0,4]에서 가운데 0을 삭제하면 어떤 식이 되나요?
3. (1+x)*(1-x)를 계수 배열로 곱하고 1차 계수가 왜 0인지 설명하세요.

힌트

1. 0차부터 3차까지 네 칸을 사용합니다.
2. 마지막 4의 위치가 바뀝니다.
3. 1×(-x)와 x×1이 같은 차수로 모입니다.

해설

1. [1,0,0,2]와 [0,3,0,-2]의 합은 [1,3], 즉 1+3x입니다.
2. [4,2,4]는 4+2x+4x²입니다. 최고차수 뒤의 0과 내부의 0은 다르게 처리해야 합니다.
3. [1,1]과 [1,-1]의 곱은 [1,0,-1], 즉 1-x²입니다. 1차의 -1과 +1이 상쇄됩니다.

흔한 오해

배열의 첫 칸이 최고차 계수라는 다른 교재의 약속을 섞지 마세요. 저장 방향을 바꾸면 덧셈 정렬·출력·평가 식도 함께 바뀝니다.

복습과 다음 연결

다음 행렬은 두 인덱스가 의미를 가진 수치 자료입니다. 롤링 해시도 다항식 형태의 계산을 사용했습니다.