카테고리

CamelACT (9)
UVa (3)
Basics (4)
Information (2)
Statistics Graph


 일반적인 행렬의 덧셈은 프로그래밍으로 할 때 모든 행과 열을 검사하여 더해주면 된다. 하지만 매우 큰 행렬에 0의 개수가 대부분을 차지하는 행렬 간의 덧셈에서는 위와 같이 프로그래밍 할 경우 불필요한 시간의 낭비가 초래된다. 따라서 0의 개수가 대부분을 차지하는 행렬을 희소행렬이라 지칭하고 이와 같은 행렬의 덧셈에 대한 새로운 계산 방법을 고안해 보자.

 희소행렬 구조체의 구성은 0이 아닌 값의 행과 열, 값으로 이루어진 element 구조체가 존재하고 SparseMatrix 구조체는 배열로 element 구조체를 갖는다. 그리고 전체 행과 열의 개수와 0이 아닌 값의 개수를 나타내는 변수를 갖는다.

 예를 들어, SparseMatrix m1 = {{{ 1,1,5 },{ 2,2,9 }}, 3,3,2 };의 경우 1행 1열에 5, 2행 2열에 9가 있고 총 행렬의 크기는 3행 3열이고 0이 아닌 값은 2개 있다는 의미이다.

 나머지 알고리즘은 이전 포스트인

[Basics]구조체를 이용한 다항식의 덧셈

과 동일하다.


#include <stdio.h>

#include <stdlib.h>

#define ROWS 3
#define COLS 3

#define MAX_TERMS 10 
typedef struct { 
    int row; 
    int col; 
    int value; 
} element; 

typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows;	// 행의 개수
	int cols;	// 열의 개수
	int terms; 	// 0이 아닌 항의 개수
} SparseMatrix;

// 일반 행렬 덧셈 함수
void sparse_matrix_add(int A[ROWS][COLS], 
		int B[ROWS][COLS], int C[ROWS][COLS])  // C=A+B
{	
	int r,c;
	for(r=0;r<ROWS;r++)
		for(c=0;c<COLS;c++)
			C[r][c] = A[r][c] + B[r][c];
}

// 희소 행렬 덧셈 함수
SparseMatrix sparse_matrix_add2(SparseMatrix a, SparseMatrix b)  // C=A+B
{	
	SparseMatrix c;
	int ca=0, cb=0, cc=0;
	// 크기가 같은지를 확인
	if( a.rows != b.rows || a.cols != b.cols ){
		fprintf(stderr,"희소행렬 크기에러\n");
		exit(1);
	}
	c.rows = a.rows;
	c.cols = a.cols;
	c.terms = 0;

	while( ca < a.terms && cb < b.terms ){
		int inda = a.data[ca].row * a.cols + a.data[ca].col;
		int indb = b.data[cb].row * b.cols + b.data[cb].col;
		if( inda < indb) {
			// b 항목이 더 나중에 와야 함
			c.data[cc++] = a.data[ca++];
		}
		else if( inda == indb ){
			// a와 b가 같은 위치
			c.data[cc].row = a.data[ca].row;
			c.data[cc].col = a.data[ca].col;
			c.data[cc++].value = a.data[ca++].value +
					      b.data[cb++].value;
		}
		else 
			c.data[cc++] = b.data[cb++];
		
	}
	// 나머지항들을 옮긴다.
	for(; ca < a.terms; ca++)
		c.data[cc++] = a.data[ca++];
	for(; cb < b.terms; cb++)
		c.data[cc++] = b.data[cb++];
	c.terms = cc;
	return c;
}
// 주함수
main()
{
	SparseMatrix m1 = {	{{ 1,1,5 },{ 2,2,9 }}, 3,3,2 };
	SparseMatrix m2 = {	{{ 0,0,5 },{ 2,2,9 }}, 3,3,2 };
	SparseMatrix m3;

	m3 = sparse_matrix_add2(m1, m2);
}



신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Basics l 2012.12.05 23:05
1 2 3 4 5 6 ··· 9 
get rsstistory! Tistory Tistory 가입하기!

티스토리 툴바