[배열] 1차원 배열, 2차원 배열, 배열응용 (ft. 다항식)

[배열]

배열 : 여러 개의 동일한 데이터 타입의 데이터를 한 번에 만들려고 할 때 사용

예를 들어 6개의 정수를 저장한 공간이 필요할 때, 배열을 사용하지 않는다면

int a1, a2, a3, a4, a5, a6;

이런 식으로 일일이 변수를 선언해야 하지만 배열을 이용한다면

int A[6];

이런 식으로 배열만 선언해주면 되는 것이다.  저렇게 선언한 배열은 인덱스(index) 번호를 가지고

작업을 할 수 있기 때문에 여러 상황에서 간단하게 작업을 용이하게 할 수 있다.

위 처럼 A[6]의 배열을 1차원 배열이라 하고 저 배열의 인덱스 번호는 0부터 5까지가 된다!

즉 첫 번째 요소는 A[0]이 되고 마지막 요소는 A[5]가 되는 것이다.

배열은 메모리의 연속된 위치에 구현된다. 첫 번째 배열 A[0]의 주소가 기본 주소가 되고 다른 요소의 주소는

배열의 요소	메모리 주소
A[0]	기본 주소 = base
A[1]	base + 1*sizeof(int)
A[2]	base + 2*sizeof(int)
A[3]	base + 3*sizeof(int)
A[4]	base + 4*sizeof(int)

2차원 배열 : 1차원 배열이 여러 개 모여서 이루어진 배열, 가로줄을 행(row), 세로줄을 열(column) 이라 한다.

int A[3][4];

이처럼 2차원 배열을 선언한다. 이와 같이 선언하면 3개의 행과 4개의 열의 배열이 만들어진다.

2차원 배열을 초기화하는 방법은 다음과 같다. 데이터가 일부만 주어진다면 앞부터 초기화된다.

int A[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

배열의 응용으로 다항식을 배열을 이용해 표현해보자.

method 1.)

첫 번째 방법은 다항식의 모든 차수에 대한 계수 값을 배열에 모두 저장하는 방법이다.

하나의 다항식이 하나의 degree(차수) 변수(인덱스번호값)와 하나의 coef(계수) 배열을 필요로 하므로 이를

묶어 하나의 구조체를 만들고 이 구조체를 이용해 다항식을 표현할 수 있을 것이다.

#define MAX_DEGREE 101                //다항식의 최대 차수 + 1
typedef struct {
    int degree;
    float coef[MAX_DEGREE];
}polynomial;
 
polynomial a = { 5, { 10, 0, 0, 0, 6, 3 }};

이 방법의 문제점은 다항식의 대부분의 항의 계수가 0일 경우엔 공간 낭비가 심하다는 것이다.

예를 들어,   다음 식의 경우 계수가 0인 항이 99개나 되기 때문이다.

이 방법의 장점으로는 다항식의 덧셈이나 뻴셈 시 같은 차수의 계수를 쉽게 찾을 수 있으므로 알고리즘이 

간단해진다는 점이다. 다항식 덧셈 함수를 구현해보자면

polynomial poly_add(polynomial A, polynomial B) {
    polynomial C;                                    //결과값이 저장될 변수
    int Ain = 0, Bin = 0, Cin = 0;                    //배열 인덱스 변수
    int degree_a = A.degree;
    int degree_b = B.degree;
    C.degree = MAX(A.degree, B.degree);                //C의 차수는 A항과 B항이 합쳐질 것이므로 둘중 큰 차수를 가지게 된다. 
 
    while (Ain <= A.degree && Bin <= B.degree) {    //인덱스 값이 차수를 넘어가지 않는 선에서 반복
        if (degree_a > degree_b) {                    //A항차수 > B항차수
            C.coef[Cin++] = A.coef[Ain++];            //다항식의 덧셈은 높은 차수(인덱스=0)부터 더해간다.
            degree_a--;                                //더해진 차수는 감소시켜가며 다음 차수로 넘어간다.
        }    
        else if (degree_a == degree_b) {                    //A항차수 = B항차수
            C.coef[Cin++] = A.coef[Ain++] + B.coef[Bin++];    //같은 차수의 항끼리 더해준다.
            degree_a--;   degree_b--;
        }
        else {                                        //B항차수 > A항차수
            C.coef[Cin++] = B.coef[Bin++];
            degree_b--;
        }
    }
    return C;
}

method 2.)

공간을 절약하기 위해 다항식에서 0이 아닌 항만을 저장하는 방식도 생각할 수 있다.

위와 같이 구현하기 위해선 지수-계수 쌍을 구조체로 선언하고 이 구조체의 배열을 생성하면 쉽게 구현된다.

#define MAX_TERMS 101
struct {
    float coef;        //계수
    int expon;        //지수
} terms[MAX_TERMS];

두 번째 방식으로 두 다항식의 덧셈 알고리즘을 생각하자면, A, B 두 다항식을 더하여 C를 구한다면

순서대로 A와 B의 각 항의 지수를 비교해서 생각할 수 있다. 

1. 지수가 같으면 A와 B의 각 항의 계수를 더하여 C로 옮기고

2. 지수가 다르면 A와 B 중에 지수가 큰 항을 C로 옮기면 될 것이다.

위 방법을 어느 한쪽의 다항식이 끝날 때까지 계속하고 남은 다항식은 그대로 C에 옮기면 된다.

위 그림과 같이 나타나도록 다항식의 덧셈 함수를 구현해보면

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable: 4996)
 
#define MAX_TERMS 101                    //다항식의 최대 지수 
struct {
    float coef;
    int expon;
}terms[MAX_TERMS] = { { 8, 3 }, { 7, 1 }, { 1, 0 }, { 9, 3 }, { 3, 2 }, { 1, 0 } };
 
int avail = 6;                        //현재 비어있는 요소의 인덱스 (즉, C항이 들어갈 자리의 처음부분)
 
void attach(float coef, int expon) { //새로운 항을 다항식에 추가하는 함수
    if (avail > MAX_TERMS) {
        fprintf(stderr, "항의 개수가 너무 많음");
        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) {  //As: 다항식 A의 처음, Ae:  다항식 A의 끝
    float tempcoef;
    *Cs = avail;
 
    while (As <= Ae && Bs <= Be) {
        if (terms[As].expon > terms[Bs].expon) {                    //A의 지수 > B의 지수
            attach(terms[As].coef, terms[As].expon);                //A의 지수와 계수를 C(인덱스=avail)에 추가하기
            As++;
        }
        else if (terms[As].expon == terms[Bs].expon) {                //A의 지수 = B의 지수
            tempcoef = terms[As].coef + terms[Bs].coef;
            if (tempcoef)                                            //tempcoef 변수의 유효성 검사
                attach(tempcoef, terms[As].expon);                    //A+B의 계수와 (A, B 둘중 하나의) 지수를 C에 추가
            As++;        Bs++;
        }
        else {                                                        //A의 지수 < B의 지수
            attach(terms[Bs].coef, terms[Bs].expon);                //B의 지수와 계수를 C(인덱스=avail)에 추가하기
            Bs++;
        }
    }
    for (; As <= Ae; As++)
        attach(terms[As].coef, terms[As].expon);                //A의 나머지 항들을 옮김
    for (; Bs <= Be; Bs++)
        attach(terms[Bs].coef, terms[Bs].expon);                //B의 나머지 항들을 옮김
 
    *Ce = avail - 1;                                            //다항식 C의 끝 (attach함수 동작 마지막에 [avail++]가 되므로 -1을 해준다
}

어려워보일 수 있지만 차근차근 변수들, 함수들을 따라 읽어보면 이해가 될 것이다.