[자료구조] Chapter2. Arrays and Structures(2)

※ 이 카테고리의 글들은 knu EK.Ryu 교수님의 <자료구조> 수업을 듣고 나름대로 필자가 정리한 글입니다.

※ 부족한 설명이 있거나, 잘못 알고 작성한 부분이 보인다면 편하게 댓글로 알려주시면 정말 감사하겠습니다😊

2.4 Polynomials

이 파트에서는 다항식의 덧셈을 구조체 배열을 사용하여 구현하는 것을 연습해 봅시다!

아래 코드는 두 개의 다항식이 주어지면 더하고 결과를 출력하는 프로그램입니다.

(1) #define과 #include 부분

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100
#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)

 

• #define MAX_TERMS 100: 다항식에서 사용할 최대 항의 개수를 100으로 정의합니다.
• #define COMPARE(x, y): 두 값을 비교하여 작으면 -1, 같으면 0, 크면 1을 반환하는 매크로입니다.

 

(2) polynomial 구조체 정의, terms 구조체 배열과 avail 변수

typedef struct {
    float coef; // 계수 (다항식 항의 숫자 부분)
    int expon;  // 지수 (다항식 항의 x의 지수 부분)
} polynomial;

polynomial terms[MAX_TERMS];
int avail = 0;

 

 

• terms: 다항식 항을 저장하는 구조체 polynomial 배열입니다. 크기는 MAX_TERMS로 정의된 100입니다.
• avail: 현재 사용할 수 있는 배열 인덱스를 나타내는 변수입니다. 새로운 항을 추가할 때 이 변수가 증가합니다.

 

(3) attach 함수

void attach(float coefficient, int exponent) {
    if (avail >= MAX_TERMS) {
        fprintf(stderr, "Too many terms in the polynomial\n");
        exit(1);
    }
    terms[avail].coef = coefficient;
    terms[avail++].expon = exponent;
}

 

 

• 새로운 항을 다항식 배열에 추가하는 함수입니다.
• 만약 배열에 더 이상 항을 추가할 수 없으면 에러 메시지를 출력하고 프로그램을 종료합니다.
• terms[avail]에 항을 추가하고 avail을 1 증가시킵니다.

 

(4) padd 함수 (다항식 덧셈 ✨)

void padd(int startA, int finishA, int startB, int finishB, int* startD, int* finishD) {
    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에 저장합니다. 이 두 변수에 포인터를 사용하는 이유는 함수 외부에서 선언된 변수의 값을 변경해야 하기 때문입니다.
• COMPARE 매크로를 사용하여 두 항의 지수를 비교하고, 한 다항식이 먼저 끝나면 나머지 다항식의 항들을 그대로 결과 다항식에 추가합니다.

 

(5) print_polynomial 함수

void print_polynomial(int start, int finish) {
    for (int i = start; i <= finish; i++) {
        if (i > start && terms[i].coef > 0) printf("+ ");
        printf("%fx^%d ", terms[i].coef, terms[i].expon);
    }
    printf("\n");
}

 

• 다항식을 출력하는 함수입니다.
• start부터 finish까지의 항을 출력하며, 양수인 항 앞에는 +를 붙여 출력합니다.

 

(6) main 함수

int main() {
    attach(4, 3);
    attach(3, 2);
    attach(5, 0);

    attach(3, 3);
    attach(1, 2);
    attach(2, 1);

    int startD, finishD;
    padd(0, 2, 3, 5, &startD, &finishD);

    print_polynomial(startD, finishD);

    return 0;
}

 

• 첫 번째 다항식 (4x³ + 3x² + 5)와 두 번째 다항식 (3x³ + 1x² + 2x)을 배열에 추가합니다.
• 두 다항식을 더한 결과를 padd 함수로 계산하고, 그 결과를 출력합니다.

 

 

2.5 Sparse matrices

Sparse matrix는 많은 원소가 0으로 이루어진 행렬을 말합니다. 행렬의 대부분의 원소가 0인 경우, 모든 원소를 저장하는 것은 메모리와 계산 효율 측면에서 비효율적입니다. 따라서, sparse matrix는 0이 아닌 원소만을 효율적으로 저장하고 처리하기 위해 다양한 방식으로 구현됩니다.

이번에는 0이 아닌 원소가 담겨 있는 행과 열, 값을 구조체 배열에 저장하는 것으로 구현했습니다.

#define MAX-TERMS 101 /* maximum number of terms +1*/
typedef struct {
	int col;
	int row;
	int value;
} term;
term a[MAX-TERMS];

 

 

 

(1) 전치 행렬 방법1 (비효율적인 시간복잡도)

#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 101
typedef struct {
	int col;
	int row;
	int value;
} term;

term a[MAX_TERMS];
term b[MAX_TERMS];

void transpose(term a[], term b[])
{
	int n, i, j, currentb;
	n = a[0].value;
	b[0].row = a[0].col;
	b[0].col = a[0].row;
	b[0].value = n;

	if (n > 0)
	{
		currentb = 1;
		for (i = 0; i < a[0].col; i++)
			for (j = 1; j <= n; j++)
				if (a[j].col == i)
				{
					b[currentb].row = a[j].col;
					b[currentb].col = a[j].row;
					b[currentb].value = a[j].value;
					currentb++;
				}
	}
}

void printMatrix(term a[])
{
	int n, i;
	n = a[0].value;
	printf("row col value\n");
	for (i = 0; i <= n; i++)
		printf("%d %d %d\n", a[i].row, a[i].col, a[i].value);
}

int main()
{
	a[0].row = 6;
	a[0].col = 6;
	a[0].value = 8;
	a[1].row = 0;
	a[1].col = 0;
	a[1].value = 15;
	a[2].row = 0;
	a[2].col = 3;
	a[2].value = 22;
	a[3].row = 0;
	a[3].col = 5;
	a[3].value = -15;
	a[4].row = 1;
	a[4].col = 1;
	a[4].value = 11;
	a[5].row = 1;
	a[5].col = 2;
	a[5].value = 3;
	a[6].row = 2;
	a[6].col = 3;
	a[6].value = -6;
	a[7].row = 4;
	a[7].col = 0;
	a[7].value = 91;
	printf("Matrix A\n");
	printMatrix(a);
	transpose(a, b);
	printf("Matrix B\n");
	printMatrix(b);
	return 0;
}

 

• 이 코드에서 transpose() 함수를 살펴봅시다.
• 첫 번째 반복문에서는 원본 행렬의 열을 기준으로 반복문을 실행하고, 두 번째 반복문에서는 원본 행렬의 모든 값들(비 - 0인 원소)에 대해서 실행합니다.
• 즉, 시간복잡도는 O(n*m) 입니다.
• 조금 더 효율적인 방법이 있을까요?

 

(2) 전치 행렬 방법2 (효율적인 시간복잡도)

void fasttranspose(term a[], term b[])
{
	int row_terms[MAX_TERMS], starting_pos[MAX_TERMS];
	int i, j, num_cols = a[0].col, num_terms = a[0].value;
	b[0].row = num_cols;
	b[0].col = a[0].row;
	b[0].value = num_terms;
	if (num_terms > 0)
	{
		for (i = 0; i < num_cols; i++)
			row_terms[i] = 0;
		for (i = 1; i <= num_terms; i++)
			row_terms[a[i].col]++;
		starting_pos[0] = 1;
		for (i = 1; i < num_cols; i++)
			starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];
		for (i = 1; i <= num_terms; i++)
		{
			j = starting_pos[a[i].col]++;
			b[j].row = a[i].col;
			b[j].col = a[i].row;
			b[j].value = a[i].value;
		}
	}
}

• 먼저, 1차원 배열 두 개를 선언합니다. (row_terms, starting_pos)
• row_terms는 i 열에 몇 개의 값이 있는지를 저장하고, starting_pos는 각 i열이 전치된 행렬에서 몇 번째 위치에서 시작하는지를 저장합니다.
• 이 배열을 반복문을 통해 먼저 생성함으로써, 전치된 행렬 작업을 수행할 때 하나의 반복문으로 구현할 수 있게 됩니다.
• 시간복잡도는 O(numCol + numTerms)으로, 이전 코드보다 효율적입니다.

 

2.6 Representation of Multidimensional Arrays

배열의 첫 번째 주소 위치를 a라고 하면, 이를 기준으로 특정 요소까지 얼마나 떨어져 있는지를 알 수 있습니다.