희소 행렬이란? 행렬의 값이 대부분 0인 행렬
일반적으로 행렬은 2차원 배열을 이용한다.
#define MAX_ROWS 100
#define MAX_COLS 100
int matrix[MAX_ROWS][MAX_COLS];
이것이 방법 1 이고.
하지만, 이 방법으로 행렬을 표현하게 된다면 다수의 항이 0일 경우에 메모리 낭비가 심하게 된다.
그래서 다른 방법을 사용할 필요가 있다.
희소 행렬을 나타내는 다른 방법
배열을 이용하되 행렬 값이 0이 아닌 노드만을 행 / 열 / 값 으로 표시하는 것이다.
이것이 방법 2 이다.
예를 들어,
이렇게 생긴 행렬이 있다고 가정해보자.
이 행렬을 새로운 방법으로 나타내면,
이렇게 나타낼 수 있다.
만약 방법 1(이차원 배열)로 행렬의 전치 연산을 한다고 생각해보자.
방법 1에서는 (i, j)의 요소와 (j, i)의 요소를 교환해주기만 하면 된다.
방법 1로 전치행렬 계산
#include <stdio.h>
#include <stdlib.h>
#define ROWS 3
#define COLS 3
//행렬 교환
void TransposMatrix(int A[ROWS][COLS], int B[ROWS][COLS]) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
B[j][i] = A[i][j]; //행렬 값 교환
}
}
}
//행렬 출력
void PrintMatrix(int A[ROWS][COLS]) {
printf("=================\n");
for(int i = 0; i < ROWS; i++) {
for(int j = 0; j < COLS; j++) {
printf("%d ", A[i][j]);
}
printf("\n");
}
}
int main(void) {
int array1[ROWS][COLS] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int array2[ROWS][COLS];
TransposMatrix(array1, array2);
PrintMatrix(array1);
PrintMatrix(array2);
return 0;
}
방법 2로 전치행렬 계산
방법 2로 전치행렬을 계산한다면, 일단 기존에 있던 배열을 A / 전치 연산한 배열을 B라고 해보자
이렇게 변경해주면 된다.
주의할 점
전치 연산을 하기 전에, 기존 방법 2에서는 행의 순서대로 저장되었다. ex) 행이 0 -> 행이 1 -> 행이 1 이 순서대로 저장되었음.
하지만, 위처럼 단순히 행값과 열값을 바꾼다면 행의 순서대로 저장되지 않는다. ex) 행이 3 -> 행이 0 -> 행이 5 순서가 맞지 않는다.
즉, B를
이런 순서로 저장되게 해야한다.
어떻게 해야할까?
방법은 이렇다.
어떤 변수를 i = 0이라고 선언한다.
우선 A에서의 열이 B에서의 행이 되므로,
i = 0을 증가시키면서, A의 열값과 비교한다.
만약 i와 A의 열값이 동일하다면 교환 후, 저장하면 된다. (순서대로 저장되게 된다.)
코드를 보면서 확인해보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100
typedef struct {
int row; //행
int col; //열
int value; //값
} element;
방법 2는, 행렬의 값이 0이 아닌 항을 '행/열/값' 으로 나타내는 방법이라고 하였다.
그러므로 element라는 구조체에 행, 열, 값을 가질 수 있는 변수를 만들어 준다.
typedef struct {
element data[MAX_TERMS];
int rows; //행의 개수
int cols; //열의 개수
int terms; //항의 개수
} SparseMatrix;
전치된 행렬을 담을 구조체를 정의한다.
이런식으로 하려고
즉, 하나의 element구조체(요소)여러개를 data배열안에 넣기 위해서 위처럼 코드 만들었음.
SparseMatrix TransposMatrix(SparseMatrix a) {
SparseMatrix b;
int bindex; //행렬 b에서 현재 저장 위치
b.rows = a.cols; //a의 열의 개수는 b의 행의 개수가 될 것임
b.cols = a.rows; //a의 행의 개수는 b의 열의 개수가 될 것임
b.terms = a.terms; //항의 개수를 동일
if(a.terms > 0) {
bindex = 0;
for(int i = 0; i < b.rows; i++) { //열을 낮은 것부터 높은 순서로 배열해야함
for(int j = 0; j < a.terms; j++) {
if(a.data[j].col == i) { //i = 0부터 증가되면서 i와 일치하는 전치되기전의 열이
//있다면, 교환하고 저장 (이부분이 순서대로 저장되는 부분)
b.data[bindex].row = a.data[j].col;
b.data[bindex].col = a.data[j].row;
b.data[bindex].value = a.data[j].value;
bindex++;
}
}
}
}
return b;
}
이 부분에서 전치가 이뤄진다.
전체적인 코드를 살펴보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100
typedef struct {
int row; //행
int col; //열
int value; //값
} element;
typedef struct {
element data[MAX_TERMS];
int rows; //행의 개수
int cols; //열의 개수
int terms; //항의 개수
} SparseMatrix;
SparseMatrix TransposMatrix(SparseMatrix a) {
SparseMatrix b;
int bindex; //행렬 b에서 현재 저장 위치
b.rows = a.cols; //a의 열의 개수는 b의 행의 개수가 될 것임
b.cols = a.rows; //a의 행의 개수는 b의 열의 개수가 될 것임
b.terms = a.terms; //항의 개수를 동일
if(a.terms > 0) {
bindex = 0;
for(int i = 0; i < b.rows; i++) { //열을 낮은 것부터 높은 순서로 배열해야함
for(int j = 0; j < a.terms; j++) {
if(a.data[j].col == i) {
b.data[bindex].row = a.data[j].col;
b.data[bindex].col = a.data[j].row;
b.data[bindex].value = a.data[j].value;
bindex++;
}
}
}
}
return b;
}
void PrintSparseMatrix(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");
}
int main(void) {
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 = TransposMatrix(m);
PrintSparseMatrix(result);
return 0;
}
(0, 3, 7)
(1, 0, 9)
(1, 5, 8)
(3, 0, 6)
(3, 1, 5)
(4, 5, 1)
(5, 2, 2)
를 전치연산 한 결과는?
실행 결과)
'자료구조(Data Structure)' 카테고리의 다른 글
이진 트리의 순회 (0) | 2023.04.26 |
---|---|
이진 트리 기본 (0) | 2023.04.04 |
C언어로 원형 연결 리스트 구현하긩 (0) | 2023.02.05 |
C언어로 연결리스트(Linked List) 구현하기 (0) | 2023.02.03 |
C언어로 리스트 구현하기 (0) | 2023.02.01 |