Overview

실제 프로그램을 작성할때 배열은 상당히 많이 쓰인다.

하지만 배열을 효율적으로 사용하기 위해 배열의 한계점을 이해하여야 한다.

순서 리스트 구조가 필요한 곳에 무조건 순차 사상으로 구현하는 배열을 사용하는 것은 현명하지 않은 결과를 가져올 수 있다.

이 포스트에서는 다항식(polynomial)문제를 풀어보면서 배열이 문제 해결의 한 방법이며, 전부가 아니라는 것을 살펴본다.

Polynomial

수학적으로 다항식은 \(ax^e\) 형식을 가진 항(term)의 합으로 정의하고 있다.

여기서 x는 변수(variable), a는 계수(coefficient), e는 지수(exponent)이다.

예를 들어 다항식 \(A(x)=2x^3+4x^2+5\) 와 다항식 \(B(x)=3x^{15}+x\)는 각각 3개의 항과 2개의 항으로 구성되어 있다.

다항식에서 제일 큰 지수를 차수(degree)라고 한다.

실제로 다항식에서는 계수가 0인 항은 제거하여 표현하지 않고, 지수가 0인 항은 변수 없이 계수만 표현한다.

ADT Polynomial
데이터 : 지수-계수의 순서 쌍 <e\(_i\) \(\in\)Exponent, a\(_i\) \(\in\)Coefficient>의 집합으로 표현된 다항식 \(p(x)=a_0x{^{e_0}}+a_1x{^{e_1}}+...+a_nx{^{e_n}}\)
연산 : p, p\(_1\), p\(_2\) \(\in\) Polynomial;
    zeroP() ::= return p(x)=0;
    isZeroP(p) ::= if(p) then return false
        else return true;
    coef(p, e) ::= if(<e, a> \(\in\) p) then return a // p 다항식에서 지수가 e인 계수 추출
        else return 0;
    maxExp(p) ::= return max(p.Exponent); // 최고차항 검색
    addTerm(p, a, e) ::= if(e \(\in\) p.Exponent) then return error
        else return p after inserting the term <e, a>
    delTerm(p, e) ::= if(e \(\in\) p.Exponent) then return p after removing the term <e, a>
        else return error;
    sMult(p, a, e) ::= return (p \(*\) ax\(^e\));
    polyAdd(p\(_1\), p\(_2\)) ::= return (p\(_1\) \(+\) p\(_2\));
    polyMult(p\(_1\), p\(_2\)) ::= return (p\(_1\) \(*\) p\(_2\));
End Polynomial

그러나 이것만으로는 요구하는 데이터 타입으로의 요건에 충족되지 못한다.

데이터와 함께 관련 연산자가 정의되어야 하는데 위 ADT는 다항식 ADT의 정의를 보여주고 있다.

여기서 p.Exponent라고 표기한 것은 다항식 p에 나타난 지수 값들을 표현한 것이다.

이 정의에서 알 수 있듯이 모든 다항식은 zeroP()와 addTerm()연산을 통해 만들 수 있다.

예를 들어 \(2x^3+4x^2+5\)는 다음과 같이 만들어진다.

addTerm(addTerm(addTerm(zeroP(), 2, 3), 4, 2), 5, 0)

이러한 연산은 어떤 특정 구현에 상관없이 다항식의 본질을 이해하는데 중요하다.

그러나 이러한 연산자를 실제로 구현하기 위해서는 먼저 몇 가지 결정을 해야한다.

여기서는 다음과 같은 3가지를 가정하였다.

모든 항은 지수의 크기에 따라 내림차순으로 표현한다.
모든 항의 지수는 다르다.
계수가 0인 항은 표함하지 않는다.

polyAdd(p\(_1\), p\(_2\))
    // p\(_3\) = p\(_1\)+p\(_2\) : 다항식 p\(_1\)과 p\(_2\)를 더한 결과 p\(_3\)을 반환
    p\(_3\) = zeroP();
    while (not isZeroP(p\(_1\)) and not isZeroP(p\(_2\))) do {
        case {
            maxExp(p\(_1\)) < maxExp(p\(_2\)) :
                p\(_3\)=addTerm(p\(_3\), coef(p\(_2\), maxExp(p\(_2\))), maxExp(p\(_2\)));
                p\(_2\)=delTerm(p\(_2\), maxExp(p\(_2\)));
            maxExp(p\(_1\)) = maxExp(p\(_2\)) :
                sum=coef(p\(_1\), maxExp(p\(_1\))) + coef(p\(_2\), maxExp(p\(_2\)));
                if (sum != 0) then p\(_3\) = addTerm(p\(_3\), sum, maxExp(p\(_1\)));
                p\(_1\) = delTerm(p\(_1\), maxExp(p\(_1\)));
                p\(_2\) = delTerm(p\(_2\), maxExp(p\(_2\)));
            maxExp(p\(_1\)) > maxExp(p\(_2\)) :
                p\(_3\) = addTerm(p\(_3\), coef(p\(_1\), maxExp(p\(_1\))), maxExp(p\(_1\)));
                p\(_1\) = delTerm(p\(_1\), maxExp(p\(_1\)));
        }
    }
    if (not isZero(p\(_1\))) then p\(_1\)의 나머지 항들을 p\(_3\)에 복사
    else if (not isZeroP(p\(_2\))) then p\(_2\)의 나머지 항들을 p\(_3\)에 복사
    return p\(_3\);
end polyAdd()

이러한 가정 하에 다항식 덧셈을 수행하는 polyAdd() 연산을 설계해보면 위 알고리즘과 같이 기술할 수 있다.

이 알고리즘은 기본적으로 두 다항식의 지수를 비교해가면서 그 결과에 따라 항들을 합병하고, 복사하는 작업의 반복으로 되어 있다.

실제로는 case문이 두 지수를 비교해 가면서 적절한 조치를 취하고 있다.

두 다항식 중 어느 하나가 먼저 소진되어 처리가 완료되면 루프를 빠져나가 또 다른 다항식의 나머지 항들을 모두 결과 다항식에 복사하는 것으로 모든 작업이 끝나게 되어 있다.

그러면 이 연산들이 처리해야 될 다항식은 어떻게 표현해야 되는지 다음으로 알 수 있다.

\[p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0\]

p(x)는 위와 같이 모든 지수의 내림차순으로 쓸 수 있고 a\(_n\)!=0 이며 n은 p의 차수이다.

이 다항식은 계수만으로 표현할 수 있다는 것을 알 수 있다.

즉, 다항식의 차수 n을 변수 degree에 별도로 저장한다면, 계수는 n+1개이기 때문에 이것은 길이가 n+1인 순서 리스트에 지수의 내림차순으로 간단하게 표현하면 된다.

이것을 1차원 배열 coef[n+1]로 표현하면 다음과 같이 된다.

fig_2

degree = n
coef[i] = a\(_{n-1}\), 0 <= i <= n

여기서 배열 coef[i]의 값은 지수가 n-i인 항의 계수 a\(_{n-1}\)가 되고, 지수 n-i를 가진 항이 없을때는 0이 저장된다.

예를 들어 coef[5]의 값이 16이면 다항식에 있는 16\(x^4\)인 항을 의미한다.

이 표현은 다항식의 덧셈이나 곱셈을 하는 연산의 알고리즘을 간단히 만들고 지수를 별도로 저장하지 않아도 되는 이점이 있다.

그러나 0이 아닌 항이 몇 개 안되는 희소 다항식인 경우에 이 p(x)표현은 공간의 낭비가 아주 심하다.

예를 들어 \(x^{1000}+1\)과 같은 다항식에 대한 p(x)표현에서는 배열의 원소 2개만 0이 아니고 나머지 999개가 모두 0이 된다.

따라서 또 다른 방법을 생각해 볼 필요가 있다.

위의 방법과 달리 다항식 p(x)에서 0이 아닌 항만 저장한다면, 다항식은 다음과 같이 b(x)로 표현할 수 있다.

\[b(x)=b_{m-1}x^{e_{m-1}}+b_{m-2}x^{e_{m-2}}+...+b_{0}x^{e_{0}}\]

여게서 m은 0이 아닌 항의 수이며, b\(_i\)는 계수, e\(_i\)는 지수로서, \(e_{m-1} > e_{m-2} > ... > e_{0}\)를 만족한다.

만일 다항식 p(x)의 계수들이 모두 0이 아니라면 b(x)로의 표현에서는 0 <= i <= n 에 대해, m=n_1, b\(_i\)=a\(_i\), 그리고 e\(_i\)=i가 된다.

반대로 a\(_n\)만 0이 아니고 나머지 항들이 모두 0이라면, m=1, b\(_0\)=a\(_n\), e\(_0\)=n이 된다.

이러한 다항식에 대해 항수 m을 별도로 저장한다면 나머지 정보는 다음과 같이 지수-계수 쌍으로 길이가 (2\(\cdot\)m)인 순서 리스트로 표현할 수 있다.

\[(e_{m-1}, b_{m-1}, e_{m-2}, b_{m-2}, ..., e_0, b_0)\]

이 b(x)의 방법으로 \(x^{1000}+1\)을 표현한다면 간단하게 (1000, 1, 0, 1)이 된다.

이렇게 0이 아닌 항에 대해서만 이 지수-계수 쌍 표현 방법을 사용하면, 실제로 다항식 연산 알고리즘은 계수를 처리하기 위해 먼저 지수를 검사해야 하는 과정때문에 복잡해진다.

물론 이 방법도 p(x) 방법보다 항상 좋은 것은 아니다.

예를 들면 다항식 \(2x^4+10x^3+x^2+6\)을 p(x), b(x) 두 방법으로 각각 표현하면 다음과 같다.

(2, 10, 1, 0, 6) (4, 2, 3, 10, 2, 1, 0, 6)

p(x) 방법으로는 리스트의 길이가 5가 되지만 b(x) 방법으로는 리스트의 길이가 8이 되어 첫 번째 p(x)방법보다 더 길어진다.

더욱이 차수가 n인 다항식에서 n+1항이 모두 0이 아닌 경우는 최악의 경우로서 b(x) 방법이 p(x) 방법보다 2배 가까운 저장 공간이 필요하게 된다.

반면에 \(x^{1000}+1\)과 같은 다항식인 경우에 대해서는 b(x) 방식보다 p(x) 방식이 200배 이상의 공간 낭비가 된다.

그러기 때문에 일반적으로 b(x) 방법을 더 선호하고 있다.

지수-계수 쌍으로 표현된 다항식을 배열로 구현한다고 할 때 순서리스트를 표현하는 1차원 배열 이외에 여러가지 선택이 있을 수 있다.

2차원 배열, term[m,2]와 같이 만들어 사용하던지, 계수와 지수를 별도로 표현하는 1차원 배열 두 개를 coef[m], exp[m]과 같이 쌍으로 만들어 사용해도 된다.

예를 들어, 다항식 \(2x^8-6x^5+10x^3+x^2-2\)에 대한 지수-계수 리스트 (8, 2, 5, -6, 3, 10, 2, 1, 0, -2)를 b(x) 방법으로 2차원 배열 p[5, 2]에 표현하면 다음과 같이 된다.

fig_3

또한 하나의 배열에 하나의 다항식뿐만 아니라, 여러 개의 다항식을 표현할 수 있다.

이 방법은 분명히 저장공간을 효율적으로 사용할 수 있지만 인덱스를 주의깊게 통제해야 되는 어려움이 있다.

참고 문서

이석호. (2004). 자료 구조와 JAVA. 정익사.

5. 다항식 추상 데이터 타입

Overview

Polynomial

참고 문서

RaP0d

Overview

Polynomial

참고 문서

Share this post