C 언어를 사용하여 정방 행렬(밀집 행렬)과 희소 행렬의 전치 연산을 각각 구현하고, 이들의 데이터 표현 방식, 메모리 효율성, 알고리즘적 특성을 비교 분석
환경
Raspberrypi 3B, 64bit, 6.12, y-ssh로 접속
정방 행렬_Square Matrix
행과 열의 개수가 같은 행렬
특징
대부분의 원소가 0이 아닌 일반적인 밀집 행렬
일반적인 2차원 배열 사용 _2D 배열(연속 메모리)
간단히 index 교환으로 수행 _ 단순 인덱스 교환
메모리 접근이 연속적이므로 일반적으로 빠름_ 메모리 사용량이 높음
이미지 처리, 선형대수 등에 사용
범용 수학 연산, 기초 행렬 연산
사용 코드
#include <stdio.h>
// 두 값 중 큰 값을 반환하는 매크로 (삼항 연산자 사용)
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
// 다항식의 최대 차수를 100차로 설정 (0차 포함 총 101개 항 저장 가능)
#define MAX_DEGREE 101
// 다항식을 표현하는 구조체
typedef struct {
int degree; // 최고차 항의 차수
float coaf[MAX_DEGREE]; // 각 항의 계수 (지수 순서대로 저장)
} polynomial;
// 두 다항식 A와 B를 더해 결과 다항식 C를 반환하는 함수
polynomial poly_add(polynomial A, polynomial B) {
polynomial C; // 결과 다항식
int Apos = 0, Bpos = 0, Cpos = 0; // 각 다항식의 현재 위치 인덱스
int degree_a = A.degree; // A 다항식의 현재 차수 추적
int degree_b = B.degree; // B 다항식의 현재 차수 추적
C.degree = MAX(A.degree, B.degree); // 결과 다항식의 차수는 큰 쪽으로
// A와 B의 모든 항을 순차적으로 비교하면서 더함
while (Apos <= A.degree && Bpos <= B.degree) {
if (degree_a > degree_b) {
// A의 항이 더 높은 차수일 경우, 그대로 결과에 복사
C.coaf[Cpos++] = A.coaf[Apos++];
degree_a--;
}
else if (degree_a == degree_b) {
// 같은 차수일 경우, 계수를 더해서 결과에 저장
C.coaf[Cpos++] = A.coaf[Apos++] + B.coaf[Bpos++];
degree_a--;
degree_b--;
}
else {
// B의 항이 더 높은 차수일 경우, 그대로 결과에 복사
C.coaf[Cpos++] = B.coaf[Bpos++];
degree_b--;
}
}
return C;
}
// 다항식을 출력하는 함수
void print_poly(polynomial p) {
for (int i = p.degree; i > 0; i--) {
// 최고차항부터 차수순으로 출력
printf("%3.1fx^%d + ", p.coaf[p.degree - i], i);
}
// 마지막 0차항 출력 (상수항)
printf("%3.1f \n", p.coaf[p.degree]);
}
int main(void) {
// 다항식 a = 3x^5 + 6x^4 + 0x^3 + 0x^2 + 0x^1 + 10
polynomial a = {5, {3, 6, 0, 0, 0, 10}};
// 다항식 b = 7x^4 + 0x^3 + 5x^2 + 0x^1 + 1
polynomial b = {4, {7, 0, 5, 0, 1}};
polynomial c;
// 각각의 다항식을 출력
print_poly(a);
print_poly(b);
// 다항식 덧셈 수행
c = poly_add(a, b);
// 결과 다항식 출력
printf("-------------\n");
print_poly(c);
return 0;
}
Sparse Matrix
대부분의 원소가 0인 성분이 매우 적거나 없는 행렬
특징
구조체 배열 등을 사용해 행, 열 값만 저장 _ 선택적 저장 가능
0이 아닌 원소만 대상으로 전치 수행 - 위치 교환
0이 많은 만큼 불필요한 연산을 줄임_ 메모리 사용량이 낮음
문서 행렬, 그래프 표현 등에 사용
대규모 데이터 처리, 희소 특성 표현
사용 코드
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100 // 희소 행렬에서 0이 아닌 항의 최대 개수
// 0이 아닌 항 하나를 나타내는 구조체
typedef struct {
int row; // 행 인덱스
int col; // 열 인덱스
int val; // 실제 값 (0이 아닌 값만 저장)
} element;
// 희소 행렬 전체를 표현하는 구조체
typedef struct {
element data[MAX_TERMS]; // 0이 아닌 항들을 저장하는 배열
int rows; // 전체 행 수
int cols; // 전체 열 수
int terms; // 0이 아닌 항의 개수
} SparseMatrix;
// 희소 행렬 전치 함수 (Transpose)
SparseMatrix matrix_transpose2(SparseMatrix a){
SparseMatrix b; // 전치 결과를 저장할 희소 행렬 b
int bindex = 0; // b의 현재 저장 위치 인덱스 초기화
// 전치 후의 행과 열 수는 서로 바뀜
b.rows = a.cols;
b.cols = a.rows;
b.terms = a.terms;
// 항이 존재할 때만 수행
if(a.terms > 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[bindex].row = a.data[i].col;
b.data[bindex].col = a.data[i].row;
b.data[bindex].val = a.data[i].val;
bindex++; // 다음 위치로 이동
}
}
}
}
return b; // 전치 결과 반환
}
// 희소 행렬을 (row, col, val) 형태로 출력
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].val);
printf("=================\n");
}
int main(void){
// 6x6 희소 행렬 m 선언 및 초기화 (총 7개의 항이 존재)
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;
}
