[자료구조] 다항식 (Polynomials)

배열을 사용하여 다항식을 관리할 수 있습니다.

많은 방법들이 있지만 대표적으로 Dense representation 과 Sparse representation이 있어요.

Dense representation은 모든 다항식의 항과 계수가 0인 모든 항을 포함하는 것을 말합니다.

Dense representation의 장점으로는 아주 간단한 연산 방법으로 다항식을 계산할 수 있다는 것입니다.

하지만 여전히 문제점이 있어요.

모든 다항식의 항과 계수가 0인 모든 항을 포함하다 보니 공간의 낭비가 생길 수 밖에 없고, 대부분의 항들이 계수가 0인 상황이 더 많을 겁니다.

그래서 Sparse representation을 사용하기도 합니다.

Sparse representation은 각각의 다항식의 항들이 지수와 계수를 포함합니다. 그리고 계수가 0인 항들은 필요로 하지 않습니다.

이때 구조체를 사용하면 편리하게 지수와 계수를 관리할 수 있어요.

#define MAX_TERMS 100

typedef struct {
  int coef;
  int expon;
} polynomial;

polynomial terms[MAX_TERMS];

지수와 계수를 멤버로 가지는 구조체를 배열로 선언하여 다항식을 관리합니다.

그렇다면 어떻게 관리하는게 좋은 방법일까요?

이해를 돕기 위해 상황을 하나 생각해보겠습니다.

현재 다항식 A와 다항식 B를 하나의 배열로 관리를 해보려고 합니다.

avail은 0부터 시작하여 terms라는 구조체 배열의 avail 번째 요소에 접근하여 다항식 A의 최고차항부터 값들을 하나씩 입력하여 줍니다. 그리고 하나씩 입력을 다 하였다면 avail의 값을 1 증가시켜 다음 인덱스로 넘어가 다항식 B의 항들을 입력하는 과정을 반복합니다. 이 과정은 아래 코드와 같습니다.

int avail = 0;

...

int starta, finisha;
  int startb, finishb;
  int startc, finishc;

  starta = avail;
  terms[avail].expon = 1000; terms[avail].coef = 2; 
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finisha = avail;
  avail++;

  startb = avail;
  terms[avail].expon = 4; terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 3; terms[avail].coef = 10;
  avail++;
  terms[avail].expon = 2; terms[avail].coef = 3;
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finishb = avail;
  avail++;

위에 있는 두 다항식을 코드로 작성하였고 이를 그림을 통해 나타낸다면 다음과 같은 결과를 얻을 수 있습니다.

이렇게 작성한다면 공간을 더욱 효율적으로 관리할 수 있게됩니다. 하지만 연산은 다소 복잡해질 수 있습니다.

예를 들어서 이러한 상황 속에서 두 다항식을 더하는 것을 고려해보겠습니다.

먼저 전체 코드를 작성해놓고 설명을 하겠습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_TERMS 100
#define COMPARE(x, y) (x < y ? -1 : (x > y ? 1 : 0))

typedef struct {
  int coef;
  int expon;
} polynomial;

// shared memory for storing polynomials
polynomial terms[MAX_TERMS];
int avail = 0;

void polynomial_add(int, int, int, int, int*, int*);
void polynomial_print(int, int);
void attach(int, int);

void main() {

  // starta and finisha defines polynomial a
  int starta, finisha;
  int startb, finishb;
  int startc, finishc;

  starta = avail;
  terms[avail].expon = 1000; terms[avail].coef = 2; 
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finisha = avail;
  avail++;

  startb = avail;
  terms[avail].expon = 4; terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 3; terms[avail].coef = 10;
  avail++;
  terms[avail].expon = 2; terms[avail].coef = 3;
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finishb = avail;
  avail++;

  polynomial_add(starta, finisha, startb, finishb, &startc, &finishc);

  polynomial_print(starta, finisha);
  polynomial_print(startb, finishb);
  polynomial_print(startc, finishc);
}

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {

  /* complete this function */
  float coefficient;

  *startd = avail;

  while(starta <= finisha && startb <= finishb) {
    switch(COMPARE(terms[starta].expon, terms[startb].expon)) {
      case -1:
        attach(terms[startb].coef,terms[startb].expon);
        startb++;
        break;
      case 0:
        coefficient = terms[starta].coef + terms[startb].coef;
        if(coefficient) attach(coefficient, terms[starta].expon);
        starta++; startb++;
        break;
      case 1:
      attach(terms[starta].coef, terms[starta].expon);
      starta++;
    }
  }

    for(;starta<=finisha;starta++) {
      attach(terms[starta].coef, terms[starta].expon);
    }

    for(;startb<=finishb;startb++) {
      attach(terms[startb].coef,terms[startb].expon);
    }

    *finishd = avail - 1;
}

void attach(int coefficient, int exponent) {
  /* add a new term to the polynomial */
  if(avail >= MAX_TERMS) {
    fprintf(stderr, "too many terms in the polynomial"); exit(1);
  }
  terms[avail].coef = coefficient;
  terms[avail++].expon = exponent;
}

void polynomial_print(int starta, int finisha) {
  int i;
  for(i = starta; i <= finisha; i++) {
    if(i == starta) printf("%dx^%d", terms[i].coef, terms[i].expon);
    else printf(" + %dx^%d", terms[i].coef, terms[i].expon);
  }
  printf("\n");
}

다소 긴데 함수 하나 하나 살펴보면 괜찮을 겁니다. 또한 위 코드 중에는 다항식 A, B를 작성한 부분도 있기 때문에 살펴볼건 그렇게 많지 않습니다.

각설하여 두 다항식을 더하는 함수를 살펴보겠습니다.

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {

  /* complete this function */
  float coefficient;

  *startd = avail;

  while(starta <= finisha && startb <= finishb) {
    switch(COMPARE(terms[starta].expon, terms[startb].expon)) {
      case -1:
        attach(terms[startb].coef,terms[startb].expon);
        startb++;
        break;
      case 0:
        coefficient = terms[starta].coef + terms[startb].coef;
        if(coefficient) attach(coefficient, terms[starta].expon);
        starta++; startb++;
        break;
      case 1:
      attach(terms[starta].coef, terms[starta].expon);
      starta++;
    }
  }

    for(;starta<=finisha;starta++) {
      attach(terms[starta].coef, terms[starta].expon);
    }

    for(;startb<=finishb;startb++) {
      attach(terms[startb].coef,terms[startb].expon);
    }

    *finishd = avail - 1;
}

현재 함수는 starta, finisha, startb, finishb와 포인터 변수 startd, finishd를 인수로 받고 있습니다.

starta와 finisha는 구조체 배열 terms에서 다항식 A가 시작하는 인덱스와 끝나는 인덱스를 말합니다.

마찬가지로 startb와 finishb는 구조체 배열 terms에서 다항식 B가 시작하는 인덱스와 끝나는 인덱스를 말합니다.

startd와 finishd에는 다항식 A,B를 더한 결과의 시작인덱스와 끝인덱스가 되겠습니다.

다항식을 살피면서 더해야하기 때문에 반복문을 사용하였습니다.

또한 스위치문을 통해서 다항식 A,B의 최고차항부터 비교를 하여 COMPARE 함수를 통해 3가지 상황을 생각했습니다.

#define COMPARE(x, y) (x < y ? -1 : (x > y ? 1 : 0))

만약 최고차항이 A가 더 크다면?
만약 최고차항이 B가 더 크다면?
만약 두 다항식의 최고차항이 같은 상황이라면?

(여기서 최고차항이라고 함은 현재 탐색 중인 항을 얘기합니다.)

이제 switch문 안으로 들어가서 3가지 상황을 더 살펴보겠습니다.

switch(COMPARE(terms[starta].expon, terms[startb].expon)) {
      case -1:
        attach(terms[startb].coef,terms[startb].expon);
        startb++;
        break;
      case 0:
        coefficient = terms[starta].coef + terms[startb].coef;
        if(coefficient) attach(coefficient, terms[starta].expon);
        starta++; startb++;
        break;
      case 1:
      attach(terms[starta].coef, terms[starta].expon);
      starta++;
    }

현재 최고차항의 지수가 다항식 B가 더 큰 상황입니다. 따라서 구조체 배열 terms의 현재위치(startb)에 다항식 B의 최고차항의 차수와 계수를 입력합니다. 그리고 다항식 B의 1번째 항은 사용했기에 다음항을 사용하기 위하여 startb++; 을 해줍니다. 다항식을 입력하는 과정은 attach함수를 사용했습니다.

void attach(int coefficient, int exponent) {
  /* add a new term to the polynomial */
  if(avail >= MAX_TERMS) {
    fprintf(stderr, "too many terms in the polynomial"); exit(1);
  }
  terms[avail].coef = coefficient;
  terms[avail++].expon = exponent;
}

계수와 지수를 입력받아 구조체 배열 terms에 입력하도록 합니다. avail은 이전 예제에서 살펴봤다시피 구조체 배열 terms에 값을 입력하기 위해 사용했던 인덱스를 가리키는 변수입니다. 현재도 두 다항식을 더한 결과를 구조체 배열 terms의 뒤에 이어붙이기 위해서 avail을 사용하여 구조체 배열 terms에 접근하였습니다.

그리고 case문은 상대적으로 위에 있는 case가 실행되면 그 아래에 있는 case들이 모두 실행되기에 break를 걸어주어야합니다.

이 case는 두 다항식의 최고차항이 같은 상황입니다. 따라서 그냥 지수를 그대로이며 두 최고차항의 계수를 더하면 되겠습니다. 하지만 두 최고차항의 계수가 1과 -1 처럼 부호가 다르고 절댓값이 같은 상황이라면 계수는 0이 됩니다. Sparse representation에서는 계수가 0인 항은 사용하지 않기 때문에 이러한 경우에는 구조체 배열 terms에 입력을 하면 안됩니다.

따라서 if 문을 사용해 두 항의 계수를 더한 값이 0이라면 if 문이 실행되지 않아 attach함수를 호출할 일이 생기지 않습니다.

만약 두 항의 계수를 더한 값이 0이 아니라면 attach함수가 실행되어 구조체 배열 terms에 지수와 계수 값을 입력하여 줍니다.

그리고 두 항을 모두 사용했기 때문에 starta와 startb를 다음 항의 비교를 위해 모두 1씩 증가시켜줍니다.

이 상황은 다항식A의 최고차항의 지수가 더 큰 상황입니다. 모든 과정은 <case -1> 과 같습니다. 다만 이번에는 다항식 B가 아닌 다항식 A에 대한 것이라는 점만 다르기 때문에 생략하겠습니다.

while문의 조건을 본다면 starta <=finisha && startb <= finishb 라는 것을 볼 수 있습니다. 즉 두 다항식 중 하나라도 먼저 모두 살펴본 다항식이 생긴다면 반복문을 종료하게 됩니다.

그 다음 마저 살펴보지 못한 다항식은 구조체 배열 terms에 작성해주면 되겠습니다.

    for(;starta<=finisha;starta++) {
      attach(terms[starta].coef, terms[starta].expon);
    }

    for(;startb<=finishb;startb++) {
      attach(terms[startb].coef,terms[startb].expon);
    }

    *finishd = avail - 1;

만약 다항식 A가 살펴보지 못한 항들이 있다면 1번째 반복문이 실행될것이며, 두번째 반복문은 startb가 이미 finishb보다 커졌지 때문에 실행되지 않습니다.

반대의 상황이라면(다항식 B가 살펴보지 못한 항들이 있다면) 2번째 반복문이 실행될것이며, 첫번째 반복문은 위와 같은 이유로 실행되지 않을 것입니다.

그리고 더해진 다항식의 마지막 인덱스에는 구조체 배열 terms에 입력을 위해 사용한 변수 avail보다 1 작은 값이 되겠습니다.

이렇게 두 다항식이 더해지는 과정을 살펴보았습니다!

저작자표시

'지식 > 자료구조' 카테고리의 다른 글

[자료구조] 문자열(Strings) (0)	2024.04.14
[자료구조] 희소 행렬 (Sparse Matrix) (1)	2024.04.07
[자료구조] 구조체와 공용체 (Structures and Unions) (1)	2024.04.07
[자료구조] 동적 할당 배열 (Dynamically Allocated Arrays) (1)	2024.04.07
[자료구조] 배열(Arrays) (2)	2024.04.07

칙칙폭폭 땡땡

[자료구조] 다항식 (Polynomials)

'지식 > 자료구조' 카테고리의 다른 글

티스토리툴바

[자료구조] 다항식 (Polynomials)

'지식 > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바