[알고리즘] 배열의 응용: 다항식 덧셈 프로그램 분석2

아래 코드는 배열을 이용한 다항식 덧셈 코드이다. 덧셈의 기능만 있으며 두 다항식에서 0이 아닌 항만을 {계수,차수} 형식으로 배열에 저장한다. 계수, 지수를 멤버로 한 구조체를 만들고 이를 배열로 생성한다.

 

하나의 배열에 다항식 A와 다항식 B를 나타내고 그 뒤에 계산을 완료한 다항식 C를 나타낼 것이다. 

이 방식의 장점은 메모리 공간을 효율적으로 사용할 수 있다. 하지만 단점으로는 구현이 복잡하다는 점이다. 

 

계산을 완료하면 위와 같은 사진처럼 배열에 정리된다.

 

 

해당 방식의 알고리즘

- 다항식 A와 B의 계수와 지수를 비교하여, 지수가 같으면 두 다항식의 계수를 더하여 C로 옮기고 다르면 A,B중 지수가 큰 항의 계수를 C로 옮긴다.

- 위와 같은 과정을 어느 한 다항식의 지수가 0이 될 때까지 반복한다.

- 한쪽의 다항식이 끝나게 되면 남아있는 항의 데이터들을 C로 옮겨주는 작업을 하면 계산이 완료된다.

 

전체 코드

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 101

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

polynomial terms[MAX_TERMS] = { {8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0} };
int avail = 6;    // c의 시작 인덱스

char compare(int a, int b) {
    if (a > b) return '>';
    else if (a == b) return '=';
    else return '<';
}

void attach(float coef, int expon) {
    if (avail > MAX_TERMS) {
        fprintf(stderr, "항의 개수가 너무 많음\n");
        exit(1);
    }
    terms[avail].coef = coef;
    terms[avail].expon = expon;
    avail++;
}

void poly_add(int As, int Ae, int Bs, int Be, int *Cs, int *Ce) {
    float tempcoef;
    *Cs = avail;

    while (As <= Ae && Bs <= Be) {
        switch (compare(terms[As].expon, terms[Bs].expon)) {
        case '>':
            attach(terms[As].coef, terms[As].expon);
            As++; break;
        case '=':
            tempcoef = terms[As].coef + terms[Bs].coef;
            if (tempcoef)    // 0 일 때 아무것도X, 0 아닐 때 attach
                attach(tempcoef, terms[As].expon);
            As++; Bs++; break;
        case '<':
            attach(terms[Bs].coef, terms[Bs].expon);
            Bs++; break;
        }
    }
    for (; As <= Ae; As++)    // A의 나머지 항들 이동
        attach(terms[As].coef, terms[As].expon);
    for (; Bs <= Be; Bs++)    // B의 나머지 항들 이동
        attach(terms[Bs].coef, terms[Bs].expon);
    *Ce = avail - 1;
}

    void print_poly(int s, int e) {
        for (int i = s; i < e; i++) {
            printf("%3.1fx^%d + ", terms[i].coef, terms[i].expon);
        }
        printf("%3.1fx^%d\n", terms[e].coef, terms[e].expon);
    }
    int main(void) {
        int As = 0, Ae = 2, Bs = 3, Be = 5, Cs, Ce;
        poly_add(As, Ae, Bs, Be, &Cs, &Ce);
        print_poly(As, Ae);
        print_poly(Bs, Be);
        print_poly(Cs, Ce);
        return 0;
    }

 

코드 분석

 

 

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

polynomial terms[MAX_TERMS] = { {8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0} };
int avail = 6;    // c의 시작 인덱스

구조체는 다항식의 계수(coef)와 지수(expon)을 멤버로 가지고 있다. 구조체의 별칭은 polynomial.

 

polynomial terms[MAX_TERMS] 는 총 101개의 구조체 배열을 선언한 것이다. terms의 데이터는 다항식 A와 B의 값들이다.

A= 8x^3 + 7x^1 + 1

B= 10x^3 + 3x^2 +1

 

avail은 c의 시작 인덱스이다. avail 값을 계속적으로 관리해줘야 C의 데이터를 넣을 위치를 지정할 수 있다.

현재 avail 값은 6이고 계산이 완료된 다항식 C의 값은 terms[6] 부터 들어갈 것이다.

 

char compare(int a, int b) {
    if (a > b) return '>';
    else if (a == b) return '=';
    else return '<';
}

두 다항식의 최고 차항을 비교하는 compare 함수이다. a와 b는 다항식 A와 B의 최고 차항을 나타낼 것이다. 

 

void attach(float coef, int expon) {
    if (avail > MAX_TERMS) {
        fprintf(stderr, "항의 개수가 너무 많음\n");
        exit(1);
    }
    terms[avail].coef = coef;
    terms[avail].expon = expon;
    avail++;
}

 계산이 완료된 다항식 C의 데이터들을 배열에 저장하는 attach 함수이다. 새로운 항을 다항식에 추가하는 작업을 해준다. 만약 새로운 다항식의 데이터가 들어가야 할 인덱스인 avail이 지정해둔 MAX_TERMS 값을 넘어서면 항의 개수가 너무 많다는 내용을 출력해준다. 오류를 방지하는 코드이다.

 

 자리가 충분하다면 계수와 지수 값을 차례대로 넣어주고 avail값을 증가시킨다.

 

void poly_add(int As, int Ae, int Bs, int Be, int *Cs, int *Ce) {
    float tempcoef;
    *Cs = avail;

    while (As <= Ae && Bs <= Be) {
        switch (compare(terms[As].expon, terms[Bs].expon)) {
        case '>':
            attach(terms[As].coef, terms[As].expon);
            As++; break;
        case '=':
            tempcoef = terms[As].coef + terms[Bs].coef;
            if (tempcoef)    // 0 일 때 아무것도X, 0 아닐 때 attach
                attach(tempcoef, terms[As].expon);
            As++; Bs++; break;
        case '<':
            attach(terms[Bs].coef, terms[Bs].expon);
            Bs++; break;
        }
    }
    for (; As <= Ae; As++)    // A의 나머지 항들 이동
        attach(terms[As].coef, terms[As].expon);
    for (; Bs <= Be; Bs++)    // B의 나머지 항들 이동
        attach(terms[Bs].coef, terms[Bs].expon);
    *Ce = avail - 1;
}

가장 핵심적인 함수인 덧셈을 해주는 poly_add함수이다.

As는 배열 안에서 다항식 A의 처음 인덱스, Ae는 다항식 A의 마지막 인덱스이다.

그렇다면 As는 0이 될것이고 Ae는 2이 될 것이다. 같은 방식으로 Bs와 Be값도 인자로 받는다.

 

*Cs와 *Ce는 덧셈을 수행하고 새로운 다항식 C의 시작과 끝 인덱스이다. 인자를 포인터로 받은 이유는 리턴 값이 없는 void 함수에서 Cs와 Ce를 계산하고 main 함수로 넘겨줄 때 변경된 값을 유지시켜 주기 위함이다. 

 

만약 포인터로 받지 않고 변수로 받을 경우 call-by-value 방식으로 인자를 받기 때문에 poly_add 함수 안에서 요리조리 바뀐 Cs와 Ce값이 유지되지 않고 다시 main 함수로 넘어갈 때 값이 초기화 된다. 이런 문제를 방지하기 위해 함수의 인자로 주소 값을 넘겨주어 원본의 값을 변경 시키는 것이다.  

 

그렇게 되면 다시 poly_add 함수에서 할당된 Cs와 Ce 값을 main 함수에서 사용할 수 있다.

 

다음으로 넘어가보자.

 

avail은 새로운 다항식이 들어갈 배열의 인덱스를 뜻한다. 이제 빈 곳에 다항식 C를 넣어야 하기 때문에 *Cs에 avail 값을 넣어준다. 포인터를 사용한 이유는 위에 설명했듯 원본 값을 변경시켜야 하기 때문이다. 그러므로 주소 값을 참조한다.

 

while문의 조건은 다항식 A 혹은 B가 끝날때까지 실행하는 것이다. while문이 실행되면서 As 혹은 Bs가 증가할 것이고 그것이 Ae 혹은 Be와 값이 같아지는 순간 while문을 벗어난다.

 

switch문에서 판별할 값은 <, >, = 이다. compare 함수를 통해 값을 받아온다. 

 

>가 리턴되었다면 A의 지수가 더 크다는 것을 의미한다. 

그렇다면 계산을 실행하지 않고 A의 계수와 지수를 attach 함수의 인수로 넘겨준다. 

attach 함수에 넘겨준 인수는 새로운 다항식 C의 값이다. 다항식 C의 데이터를 배열의 빈 곳 중 가장 앞에 넣는다.

As++를 해주는 이유는 해당 항의 계산은 끝났고 다음 항을 비교하기 위함이다.

 

=가 리턴되었다면 A와 B의 지수가 같다는 뜻이다.

그렇다면 둘의 계수끼리 더한다. 더한 값을 tempcoef에 잠시 넣어준다.

if문의 조건은 tempcoef이다. tempcoef가 0일 경우 false가 되기 때문에 if문을 실행하지 않고 그 외에 경우는 if문을 실행한다.

만약 더한 값이 0이면 해당 항은 사라지기 때문에 if문을 실행하지 않고 다음 while문을 돌고, 그렇지 않을 경우 계산된 값을 attach함수에 이자로 넘겨주어 다항식 C에 정보를 넣는다. 

A와 B의 항 모두 계산이 끝났기 때문에 As++, Bs++를 해준다.

 

<가 리턴되었다면 B의 지수가 더 크다는 뜻이다.

위에 설명했듯 >이 리턴되었을 때와 같은 방식으로 작동한다.

 

while문이 끝났다면 다항식 A 혹은 B의 다항식이 끝났다는 얘기이다. 

그렇다면 몇가지 경우의 수가 있는데

1. A의 다항식은 계산할 항이 남았다.

2. B의 다항식은 계한할 항이 남았다.

3. A와 B 다항식 모두 계산이 끝났다.

 

이 3가지 경우를 위해 for문을 돌려준다.

 

for (; As <= Ae; As++)    // A의 나머지 항들 이동
        attach(terms[As].coef, terms[As].expon);
    for (; Bs <= Be; Bs++)    // B의 나머지 항들 이동
        attach(terms[Bs].coef, terms[Bs].expon);

 

초기값에 대한 조건이 없는 이유는 새로운 변수를 사용하지 않고 원래 존재하던 변수를 사용해 조건을 만들었기 때문이다.

남은 항들은 따로 덧셈을 할 필요가 없기 때문에 그대로 다항식 C로 옮겨주면 된다.

 

 void print_poly(int s, int e) {
        for (int i = s; i < e; i++) {
            printf("%3.1fx^%d + ", terms[i].coef, terms[i].expon);
        }
        printf("%3.1fx^%d\n", terms[e].coef, terms[e].expon);
    }

print_poly는 최고차항과 최소차항의 인덱스 값을 인자로 받아 출력해주는 함수이다.