[C/C++]전치행렬, 희소행렬 transpose matrix, sparse matrix

이번에는 2차원 배열 형태인 행렬을 사용합니다.

전치행렬을 두 가지로 표현해볼 텐데요, 하나는 일반적인 행렬의 전치행렬, 다른 하나는 희소행렬의 전치행렬입니다.

▶전치행렬-일반

일반형태의 전치행렬은 굉장히 간단합니다. 행의 위치와 열의 위치를 바꿔주면 되니까요.

#include <stdio.h>
#define ROWS 3
#define COLS 3

void matrix_print(int A[ROWS][COLS]) {
	for (int r = 0; r < ROWS; r++) {
		for (int c = 0; c < COLS; c++) {
			printf("%d ", A[r][c]);
		}
		printf("\n");
	}
}

일단 분석할게 없는 코드 뭉텅이 입니다. 이중 for를 이용해 행렬을 출력합니다.

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

전치행렬로 만드는 transpose함수입니다. A가 원행렬, B가 전치행렬입니다. 전치행렬은 (x,y)에 있던 요소가 (y,x)에 있게 되는 것이므로 인덱스만 바꿔 저장해주면 됩니다. 반환값이 없는 이유는 배열을 인자로 사용하기 때문인데요, 배열을 인자로 사용하면 포인터를 사용하는 것과 같아 복사가 아닌 원래 값에 영향을 줍니다.

int main() {
	int arr1[ROWS][COLS] = {
		{2,3,0},
		{8,9,1},
		{7,0,5}
	};
	int arr2[ROWS][COLS] = {0};
	matrix_transpose(arr1, arr2);
	matrix_print(arr1);
	matrix_print(arr2);
	gets();

	return 0;
}

결과 창을 보여드리겠습니다.

열이 행의 위치로(행이 열의 위치로) 이동한 모습을 볼 수 있습니다.

값이 가득 차있거나, 80%이상이 차있는 행렬들은 이렇게 일반적인 방법을 통해 전치행렬로 만들어주면 되지만, 희소행렬같은 경우에는 비용이 너무 많이 발생하기 때문에 다항식 덧셈 두번째 방법에서 사용했던 '항'으로 접근해야됩니다.

▶전치행렬-희소행렬

#include <stdio.h>
#define MAX_TERMS 100

void matrix_print(SparseMatrix a) {
	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);
	}
}

가장 안중요한 코드블럭입니다. 뒤에 나오겠지만 구조체의 멤버가 구조체인 경우 a.data[i].row 와 같은 형태를 볼 수 있습니다.

typedef struct {
	int row;
	int col;
	int value;
}element;

typedef struct SparseMatrix{
	element data[MAX_TERMS];
	int rows;
	int cols;
	int terms;
}SparseMatrix;

이 블럭이 희소행렬의 전치행렬을 90%담당하고 있다고 봐도 과언이 아닙니다. 첫번째 구조체는 항의 요소를 의미합니다. 이게 SparseMatrix의 data에 들어가게 되는 것이죠.

SparseMatrix matrix_transpose(SparseMatrix a) {
	SparseMatrix b;
	int idx_b;
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;

	if (a.terms > 0) {
		idx_b = 0;
		for (int c = 0; c < a.cols; c++) {
			for (int i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {
					b.data[idx_b].row = a.data[i].col;
					b.data[idx_b].col = a.data[i].row;
					b.data[idx_b].value = a.data[i].value;
					idx_b++;
				}
			}
		}
	}
	return b;
}

전치행렬화 시켜주는 함수입니다. 우선 행, 열, 항의 총 개수를 복사해줍니다.

이중for문의 기준은 상관없습니다. rows나 cols로 하면 되죠. col의 최대값이 cols가 될테니 거기에 초점을 맞추면 됩니다. 하나의 열에 존재하는 항에 대해 행과 열을 바꾸고 값은 그대로 줍니다.