chapter 2-2(Sparse Matrix) : 구조체, 배열, 포인터

Sparse Matrix는 희소행렬이라고도 하며 행렬 원소가 0이 많은 것을 의미합니다.

이렇게 되면 쓸데 없이 많은 메모리를 사용하게 됩니다.

예를들어

(방법 1)

    0 1  2  3  4  5

0  0  0  0  7  0  0

1  9  0  0  0  0  8

2  0  0  0  0  0  0

3  6  5  0  0  0  0 

4  0  0  0  0  0  1

5  0  0  2  0  0  0

이러한 2차원 배열은 0이라는 쓸모없는 원소를 저장하기 위해 메모리를 6*6의 크기를 사용합니다.

이를 0을 제외한 (행, 열, 값)으로 표현하면 좀더 메모리를 절약할 수 있습니다.

(방법 2)

   행 열 값

0  0  3  7

1  1  0  9

2  1  5  8

3  3  0  6

4  3  1  5

5  4  5  1

6  5  2  2

이렇게 7*3의 크기를 가지고 행렬을 표현 할 수 있습니다.

하지만 이러한 방법도 예외의 행렬에서는 쓸모 없을 수 있습니다.

만약 행렬의 전치연산(transpose) 연산을 구현하는 겨우 방법 2는 많은 코딩을 요구합니다.

반면에 방법 1은 그냥 배열의 요소 (i, j)를 (j, i)로 바꾸기만 하면 됩니다.

void matrix_transpose(int A[][3], int B[][3]) {
	for (int r = 0; r < 3; r++) {
		for (int c = 0; c < 3; c++) {
			B[c][r] = A[r][c];
		}
	}
}

코드는 이와 같습니다.  A의 행렬을 B의 행렬에 옮겨 주면 됩니다.

---

이제 방법2를 전치연산(transpose)을 하는 방법을 알아 보겠습니다.

typedef struct {
	int row; //행
	int col; //열
	int value; //값
}element;
typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows;
	int cols;
	int terms; //항의 개수
}SparseMatrix;

구조체를 사용하여 행, 열, 값을 포함하는 element라는 새로운 type을 만들어줍니다.

그 다음 SparseMatrix라는 구조체를 만들어 주어 모든 데이터를 저장하는 곳을 만들어 줍니다.

SparseMatrix m = {
		{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},
		6, //행
		6, //열
		7 //항의 개수
	};

SparseMatrix에 데이터를 삽입해줍니다. 

SparseMatrix matrix_transpose2(SparseMatrix a) {
	SparseMatrix b;

	int bindex; //행렬 b에서 현재저장위치
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;

	if (a.terms > 0) {
		bindex = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {//A의 열이 0인것부터 차례대로 선별
					b.data[bindex].row = a.data[i].col;
					b.data[bindex].col = a.data[i].row;
					b.data[bindex].value = a.data[i].value;
					bindex++; 
				}
			}
		}
	}
	return b;
}

전치행렬을 수행하는 함수 입니다.

transpose한 배열을 새로 저장할 SparseMatrix b를 선언해 줍니다.

bindex변수는 행렬 b의 저장위치를 가리키는 변수입니다.

행과 열을 열과 행으로 바꿔주어야 하므로 열의 숫자가 작은 순서대로 정렬해주어야 합니다.

따라서 열이 0인 수부터 선별해서  행렬 b에 삽입해줍니다.

첫번째 for문은 0부터 행렬 a의 열까지 

두번째 for문은 0부터 행렬 a의 항까지 반복해줍니다.

---

전체코드입니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_TERMS 101
typedef struct {
	int row; //행
	int col; //열
	int value; //값
}element;
typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows;
	int cols;
	int terms; //항의 개수
}SparseMatrix;
SparseMatrix matrix_transpose2(SparseMatrix a);
void matrix_print(SparseMatrix a);
int main() {
	SparseMatrix m = {
		{{0,3,7},{1,0,9},{1,5,8},{3,0,6},{3,1,5},{4,5,1},{5,2,2}},
		6,
		6,
		7
	};
	SparseMatrix result;

	result = matrix_transpose2(m);
	matrix_print(result);

	return 0;
}
SparseMatrix matrix_transpose2(SparseMatrix a) {
	SparseMatrix b;

	int bindex; //행렬 b에서 현재저장위치
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;

	if (a.terms > 0) {
		bindex = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {//A의 열이 0인것부터 차례대로 선별
					b.data[bindex].row = a.data[i].col;
					b.data[bindex].col = a.data[i].row;
					b.data[bindex].value = a.data[i].value;
					bindex++; 
				}
			}
		}
	}
	return b;
}
void matrix_print(SparseMatrix a) {
	printf("===============================\n");
	for (int i = 0; i < a.terms; i++) {
		printf("(%d, %d, %d)\n", a.data[i].row, a.data[i].col, a.data[i].value);
	}
	printf("================================\n");
}

---

이러한 전치행렬 알고리즘은 이중 for문이 돌아가기 때문에 시간복잡도가 O(N^2)으로 너무 느리게 돌아갑니다.

따라서 더빠른 알고리즘을 구현할 필요가 있습니다.

각 열(Column)이 저장될 곳을 미리 파악하는 것입니다.

그러므로 열(Column) 인덱스 저장을 위한 추가 적인 공간을 사용해야 합니다.

      A                                                        B

  행 열 값                                               행 열 값

0  6  6  7                                             0  6  6  7

1  0  3  7                                             1  0  1  9

2  1  0  9                                             2  0  3  6

3  1  5  8                                             3  1  3  5

4  3  0  6                    →                      4  2  5  2

5  3  1  5                                             5  3  0  7

6  4  5  1                                             6  5  1  8

7  5  2  2                                             7  5  4  1

A와 B의 행렬의 맨위에 행은 원래있던 행열의 정보를 알려주는 행입니다.

원래 행렬이 6*6 이고 0이 아닌 항의 개수는 7이므로 6 6 7 을 맨위에 행으로 설정합니다.

그 다음 1번행렬부터 0이아닌 항의 데이터가 들어갑니다.

결국 맨위에 행만 늘어난거고 나머지 밑의 행렬은 그 전과 동일합니다.

row_terms 배열은 행렬 A에서 0이 아닌 항을 가진 열들이 각 몇번 나오는지 저장합니다.

따라서 A의 0번째 열은 2번 1번째 열은 1번 ...... 나옵니다.

rows_terms

            0                        1                        2                       3                        4                        5

2

1

1

1

0

2

starting_pos는 행렬 A에서 0번째 열을 제외한 1, 2, 3...n번째 열에게 바로 앞에 있던 열들이 몇번 나오는지 알려줍니다.

즉 들어가야할 열의 자리를 알려줍니다.

0번째 열앞에 맨위에 행(행렬의 정보)이 나오므로 1이 들어가고 

1번째 열앞에 맨위에 행(1) + 0번째 행의 개수(2) 이있으므로 3이 들어간다.

starting_pos

            0                       1                         2                       3                        4                        5           

1

3

4

5

6

6

따라서 행렬 A의 2번째 열에게 지금까지 0번째 열(2개), 1번째 열(1개) 나왔으므로 알려준 숫자는 2 + 1 = 3입니다.

그러므로 2번째 열은 3보다 1큰 수

즉, B의 4번째 행에 전치(transpose)해서 들어가야합니다.

int row_terms[MAX_COL], starting_pos[MAX_COL];
int num_col = A[0].col;
int num_terms = A[0].value;

B[0].row = num_col;
B[0].col = A[0].row;
B[0].value = num_terms;

먼저 row_terms 배열과 starting_pos 배열을 선언합니다.

새로운 변수 num_col을 만들어 그곳에다 A[0].col 의 값을 넣고 num_terms에다가 A[0].value를 삽입합니다.

행렬의 정보를 저장하는 것입니다. 

그 정보를 term B[0] 에다가 모두 집어 넣어 줍니다.

위에 그림에서는 행 6 열 6 항 7 이므로 

A[0].row = B[0].col =6

A[0].col = B[0].row =6

A[0].value = B[0].value =7 

초기화 해줍니다.

if (num_terms > 0) {
		for (int i = 0; i < num_col; i++) 
			row_terms[i] = 0; //A행렬의 열 개수만큼 row_terms배열 0으로 초기화
		for (int i = 1; i <= num_terms; i++)
			row_terms[A[i].col]++;  //A 행렬의 열 인덱스에 해당하는 
		starting_pos[0] = 1; //맨위에 행(정보)가 무조건 1개 있기 떄문이다.
		//현재들어갈 행의 위치 = 지금까지 있었던 행의 개수 + 바로 직전에 행의개수
		for (int i = 1; i < num_col; i++) 
			starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];
		//B행렬에 삽입
		for (int i = 1; i <= num_terms; i++) {
			int j = starting_pos[A[i].col]++; //j에는 B행렬에 들어갈 인덱스 번호
			B[j].row = A[i].col;
			B[j].col = A[i].row;
			B[j].value = A[i].value;
		}	
	}

num_terms는 행렬의 0이 아닌 항의 개수 이므로 만약 0이 아닌 항의 개수가 0보다 작거나 같으면 모든 항이 0이므로 

필요가 없어집니다.

num_terms가 0보다 크면 정상적으로 if문안으로 들어갑니다.

먼저 row_terms 배열을 A행렬의 열 갯수 만큼 0으로 초기화 합니다.

 

그 다음 for문은 term A의 열의 번호에 따라 row_terms 배열의 값을 ++ 해주는 것입니다.

row_terms 배열은 term A의 번호에 따른 열이 0이 아닌 항의 갯수를 나타내기 때문입니다.

따라서 for문이 끝나게 되면 row_terms 배열에는 각 인덱스 번호마다 A행렬의 열의 번호에 따른 0이아닌 항의개수가  저장됩니다.

예를 들어 A의 0번째 행중에서 항의 값이 0이아닌 항의 갯수는 2개 이므로

row_terms[0] = 2 가 됩니다.

 

그 다음 starting_pos[0]을 1로 초기화 해줍니다.

A[0]의 row, col, value의 값은 행렬의 정보를 저장하기 떄문에

무조건 바로 앞에 있는 행을 1칸 사용하기 떄문입니다.

 

그 다음 for문은 starting_pos배열을 새로 초기화 해주는 작업입니다.

starting_pos 배열은 처음부터 바로 직전에 있던 열의 갯수를 저장하므로 

stating_pos[i-1]은 지금까지 열의 갯수이고 row_terms[i-1]은 바로 전에 있는 열의 갯수이므로

그 둘을 합하면 지금까지 있었던 행의 개수 + 바로 직전에 행의 개수 입니다.

예를 들어 starting_pos[1] = starting_pos[0] (1) + row_terms[0] (2) =3이 됩니다.

따라서 1번 열은 B의 행렬의 3번째 인덱스 부터 들어가는 것을 알려 주는 것입니다.

 

마지막 for문은 지금까지 정보를 B행렬에 삽입하는 과정입니다.

이미 B행렬의 0번째 인덱스는 행렬의 정보가 들어가 있으므로 for문에서 i=1부터 시작하게 됩니다.

변수 j는 B행렬에 들어갈 인덱스 번호를 의미합니다.

starting_pos[A[i].col] 은 B행렬에 들어갈 인덱스  번호를 가리키므로 작업이 다끝나고 ++연산을 해줍니다.

A행렬의 열이 여러개 일 수 있기때문입니다.

위에 행렬도 열의 번호가 0인 행렬이 2개 이므로 

번호가 0인 첫번째 열은 starting_pos[0] = 1 로 인해 B행렬 [1] 위치에 들어가고 ++해줍니다.

또 번호가 0인 두번째 열은 아까전에 ++연산을 해줬으므로 starting_pos[0] = 2이므로 B행렬의 [2] 위치에 들어갑니다.

이렇게 반복을 끝나면 fast_transpose 연산이 끝나게 됩니다. 

 

이러한 알고리즘은 아까 봤던 방법 2 에비해 메모리는 더 소비할지 몰라도 시간에 있어서는 더 빠른 알고리즘을

사용합니다. 간단히 보면 이중 for문 보다 1중 for문을 다양하게 사용하기 때문에 시간복잡도는 O(N)이 나오게 됩니다.

 

---

입력 부분 입니다.

void read(term a[], int m, int n) {
	int k, item, p;
	a[0].row = m;
	a[0].col = n;
	k = 1;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &item);
			if (item == 0)
				continue;
			a[k].row = i;
			a[k].col = j;
			a[k].value = item;
			k++;
		}
	}
	a[0].value = k-1 ;
}

 먼저 main 함수에서 행의 갯수 m 과 열의 갯수 n을 입력받아 함수로 수행합니다.

변수 k는 0이 아닌 항들의 갯수를 세기 위함입니다.

변수 item은 행렬의 값을 입력 받을 것입니다. 아까 행렬은 6 X 6이므로 총 36개의 item을 입력 받을 것입니다.

먼저 term a의  0번째 행은 행렬의 정보를 저장하므로 

a[0].row = m(행의 갯수)

a[0].col = n(열의 갯수)

k = 1(이미 term A[0]에 행렬의 정보가 들어가 있기 때문에 k=1부터 세기 시작하기 때문입니다.)

로 초기화 해줍니다.

그 다음 이중 for문으로 m X n개로 item(행렬의 값)을 입력받습니다.

하지만 우리는 0이 아닌 항 만 필요하므로 item=0을 입력받으면 continue함수를 사용해 무시해주고 다음 item을        입력 받습니다.

0이 아닌 항을 입력 받을 때 마다 k++해줍니다.

이중 for문이 끝나면 k= 8이 되므로 0이 아닌 항의 갯수는 7이기 때문에 k-1을 해주어 

a[0].value(행렬의 0이 아닌 항의 갯수) 에다가 삽입해줍니다.

그러면 term A의 정보가 모두 입력을 받게 됩니다.

---

출력 부분 입니다.

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

for문을 사용해 i는 0부터 시작해서 a[0].value(7) 까지 총 8개의 행을 출력합니다.

0이 아닌 항의 갯수는 7이지만 term A 의 맨위에 행은 행렬의 정보가 저장되 있기 때문입니다.

따라서 맨위에 행(1) + 0이 아닌 항의 갯수(7) 을 포함해 8개를 출력해줍니다.

---

main 함수 부부입니다.

int main() {
	int m, n;
	scanf("%d%d", &m, &n); //각 행렬의 행과 열을 입력받는다
	term A[MAX];
	term B[MAX];
	read(A, m, n);//각 행렬의 value값을 입력받는다
	fast_transpose(A, B);
	matrix_print(B); //행렬의 출력

	return 0;
}

---

전체 코드입니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 101
#define MAX_TERMS 101
#define MAX_COL 50
typedef struct {
	int row;
	int col;
	int value;
}term;
void fast_transpose(term A[], term B[]);
void matrix_print(term a[]);
void read(term a[], int m, int n);
int main() {
	int m, n;
	scanf("%d%d", &m, &n); //각 행렬의 행과 열을 입력받는다
	term A[MAX];
	term B[MAX];

	read(A, m, n);//각 행렬의 value값을 입력받는다
	
	fast_transpose(A, B);
	matrix_print(B); //행렬의 출력

	return 0;
}
void fast_transpose(term A[], term B[]) {
	int row_terms[MAX_COL], starting_pos[MAX_COL];
	int num_col = A[0].col;
	int num_terms = A[0].value;

	B[0].row = num_col;
	B[0].col = A[0].row;
	B[0].value = num_terms;

	if (num_terms > 0) {
		for (int i = 0; i < num_col; i++) 
			row_terms[i] = 0; //A행렬의 열 개수만큼 row_terms배열 0으로 초기화
		for (int i = 1; i <= num_terms; i++)
			row_terms[A[i].col]++;  //A 행렬의 열 인덱스에 해당하는 
		starting_pos[0] = 1; //맨위에 행(정보)가 무조건 1개 있기 떄문이다.
		//현재들어갈 행의 위치 = 지금까지 있었던 행의 개수 + 바로 직전에 행의개수
		for (int i = 1; i < num_col; i++) 
			starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];
		//B행렬에 삽입
		for (int i = 1; i <= num_terms; i++) {
			int j = starting_pos[A[i].col]++; //j에는 B행렬에 들어갈 인덱스 번호
			B[j].row = A[i].col;
			B[j].col = A[i].row;
			B[j].value = A[i].value;
		}	
	}
}
void matrix_print(term a[]) {
	printf("===============================\n");
	for (int i = 0; i <= a[0].value; i++) {
		printf("(%d, %d, %d)\n", a[i].row, a[i].col, a[i].value);
	}
	printf("================================\n");
}
void read(term a[], int m, int n) {
	int k, item, p;
	a[0].row = m;
	a[0].col = n;
	k = 1;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &item);
			if (item == 0)
				continue;
			a[k].row = i;
			a[k].col = j;
			a[k].value = item;
			k++;
		}
	}
	a[0].value = k-1 ;
}