typedef struct
{
int degree;
float coef[MAX_DEGREE];
}polynomial;
polynomial a = { 5, {10, 0, 0, 0, 6, 3} };
구현 소스코드
#include<stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAX_DEGREE 101
typedef struct
{
int degree;
float coef[MAX_DEGREE];
}polynomial;
polynomial poly_add1(polynomial a, polynomial b)
{
polynomial c;
int apos = 0, bpos = 0, cpos = 0;
int degree_a = a.degree;
int degree_b = b.degree;
c.degree = MAX(a.degree, b.degree);
while (apos <= a.degree && bpos <= b.degree)
{
if (degree_a > degree_b)
{
c.coef[cpos++] = a.coef[apos++];
degree_a--;
}
else if (degree_a == degree_b)
{
c.coef[cpos++] = a.coef[apos++] + b.coef[bpos++];
degree_a--; degree_b--;
}
else
{
c.coef[cpos++] = b.coef[bpos++];
degree_b--;
}
}
return c;
}
int main()
{
polynomial a = { 3,{8,0,7,1} };
polynomial b = { 3,{10,3,0,1} };
polynomial c;
c = poly_add1(a, b);
printf("%d\n", c.degree);
for (int i = 0; i < c.degree + 1; i++)
{
printf("%f ", c.coef[i]);
}
}
- 자료구조 설계 #2
cf) 설계 #1 에서 \(10x^{1000}+1\)이 경우, 1000+1개의 공간 중 2개만 사용하는 문제점이 있다. 그러므로 계수가 0이 아닌 항을 (계수, 차수) 쌍으로 저장하는 자료구조를 설계하자.
typedef struct
{
float coef;
int expon;
}polynomial;
polynomial terms[MAX_TERM] = { {8,3},{7,1},{1,0},{10,3},{3,2},{1,0} };
int avail = 6;
구현 소스코드
#include<stdio.h>
#include<stdlib.h>
#define MAX_TERM 101
typedef struct
{
float coef;
int expon;
}polynomial;
polynomial terms[MAX_TERM] = { {8,3},{7,1},{1,0},{10,3},{3,2},{1,0} };
int avail = 6;
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_TERM) {
fprintf(stderr, "항의 개수가 너무 많음\n");
exit(1);
}
terms[avail].coef = coef;
terms[avail++].expon = expon;
}
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 '>': // A의 차수 > B의 차수
attach(terms[As].coef, terms[As].expon);
As++; break;
case '=': // A의 차수 == B의 차수
tempcoef = terms[As].coef + terms[Bs].coef;
if (tempcoef)
attach(tempcoef, terms[As].expon);
As++; Bs++; break;
case '<': // A의 차수 < B의 차수
attach(terms[Bs].coef, terms[Bs].expon);
Bs++; break;
}
// A의 나머지 항들을 이동함
for (; As <= Ae; As++)
attach(terms[As].coef, terms[As].expon);
// B의 나머지 항들을 이동함
for (; Bs <= Be; Bs++)
attach(terms[Bs].coef, terms[Bs].expon);
*Ce = avail - 1;
}
int main()
{
int Cs, Ce;
poly_add(0, 2, 3, 5, &Cs, &Ce);
for (int i = 0; i < avail; i++)
{
printf("%1.0f %d\n", terms[i].coef, terms[i].expon);
}
}
* 알고리즘의 시간복잡도 - m : 다항식 A의 0이 아닌 항 수 - n : 다항식 B의 0이 아닌 항 수 - Best Case : 두 다항식의 차수가 일치할 때, O(m) ( = O(n) ) - Worst Case : 두 다항식의 차수가 모두 불일치 할 때, O(m+n) ex) 다항식 A의 차수는 짝수, 다항식 B의 차수는 홀수
2. 희소행렬 전치
희소행렬이란 행렬의 원소 중에 많은 항들이 '0' 으로 구성되어 있는 행렬이다. 이를 2차원 배열로 모두 표현한다면 메모리 공간을 낭비하는 문제가 발생한다. but, 아래의 자료구조로 희소행렬을 설계한다면 각종 행렬 연산들의 구현이 복잡해진다는 단점이 있다.
- 희소행렬 자료구조 설계
<행, 열, value>을 저장하는 3-tuple로 0이 아닌 항만 저장한다. 튜플의 0번째 값은 <행의 수, 열의 수, 0이 아닌 값들의 수> 로 저장한다.
typedef struct {
int row;
int col;
int value;
} term;
term a[MAX_TERM];
- 희소행렬 전치 #1
열 j에 있는 모든 원소에 대해 <i, j, value> → <j, i, value> 저장 구현 소스코드
#include<stdio.h>
#include<stdlib.h>
#define MAX_TERM 101
typedef struct {
int row;
int col;
int value;
} term;
term a[MAX_TERM] = { {6, 6, 7}, {0, 3, 7}, {1, 0, 9}, {1, 5, 8}, {3, 0, 6}, {3, 1, 5}, {4, 5, 1}, {5, 2, 2} };
void transpose(term a[], term b[])
{
int n, i, j, currentb;
n = a[0].value; /* 총 원소 수 */
b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */
b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */
b[0].value = n;
if (n > 0) { /* 0이 아닌 행렬 */
currentb = 1;
for (i = 0; i < a[0].col; i++) /* a에서 열별로 전치*/
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++;
}
}
}
int main()
{
term b[MAX_TERM];
transpose(a, b);
for (int i = 0; i <= b[0].value; i++) {
printf("(%d, %d, %d) \n", b[i].row, b[i].col, b[i].value);
}
}
* 공간 및 시간복잡도 - elements : 0이 아닌 원소의 수 - 공간복잡도 : O(elements) - 시간복잡도 : O(columns∙elements)
- 희소행렬 전치 #2 (개선방법)
약간의 추가 메모리를 소요하면서 시간복잡도를 O(columns+elements)로 개선한 방법 rowTerms 배열 : A의 열 j 값의 갯수를 해당 인덱스에 추가한 배열 (ex) 행렬 A의 0의 갯수 : 2 / 1의 갯수 : 1 / ... / 5의 갯수 : 2 startingPos 배열 : 해당 인덱스의 값을 전치할 때 시작할 지점을 넣은 배열
구현 소스코드
#include<stdio.h>
#include<stdlib.h>
#define MAX_TERM 101
#define MAX_COL 50
typedef struct {
int row;
int col;
int value;
} term;
term a[MAX_TERM] = { {6, 6, 7}, {0, 3, 7}, {1, 0, 9}, {1, 5, 8}, {3, 0, 6}, {3, 1, 5}, {4, 5, 1}, {5, 2, 2} };
void transpose2(term a[], term b[])
{
int rowTerms[MAX_COL], startingPos[MAX_COL];
int i, j, numCols = a[0].col, numTerms = a[0].value;
b[0].row = numCols; b[0].col = a[0].row;
b[0].value = numTerms;
if (numTerms > 0) {
for (i = 0; i < numCols; i++)
rowTerms[i] = 0;
for (i = 1; i <= numTerms; i++)
rowTerms[a[i].col]++;
startingPos[0] = 1;
for (i = 1; i < numCols; i++)
startingPos[i] = startingPos[i - 1] + rowTerms[i - 1];
for (i = 1; i <= numTerms; i++) {
j = startingPos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
}
}
int main()
{
term b[MAX_TERM];
transpose2(a, b);
for (int i = 0; i <= b[0].value; i++) {
printf("(%d, %d, %d) \n", b[i].row, b[i].col, b[i].value);
}
}
