희소행렬A의 전치행렬B를 구하는 2번째 알고리즘을 구연하라

• 입력

  

• 출력

  • 입력으로 주어진 희소 행렬 Sparse_A를 이용해 전치행렬 S_b를 계산한다.
  • S_b에 저장한 정보를 이용하여 0을 포함한 전치행렬 전체 항을 화면에 출력한다.

• 조건

  • Element* Transpose_Triple1(Element S_a[]) 함수 구현
  • void Print_Sparse_Mat (Element arr[]) 함수 구현

1.2에서 했던 알고리즘이 수행시간과 수행공간이 비효율적인 이유는 이차원 배열 사용으로 인해 이중 for문을 사용했기 때문인데 이번 알고리즘은 수행공간을 고려하나 수행시간을 고려하지 않기 때문에 이차원 배열을 일차원 배열에 저장하는 방법을 사용하였다.

S_a[0]에 행렬의 크기와 0아닌 가치의 개수를 정한다. 그리고 S_a[0]를 이용하여 행과 열을 바꾸어 전치 행렬 S_b[0]에 저장한다.

#include <stdio.h>

#define Max_Element 8

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

Element* Transpose_Triple1(Element S_a[]) {
	static Element S_b[Max_Element];
	int number = S_a[0].value;
	/*0번째 배열에 행렬의 크기와 0이 아닌 값의 개수 저장*/
	S_b[0].value = number;
	S_b[0].row = S_a[0].row;
	S_b[0].col = S_a[0].col;
	if (number > 0) {
		/*S_b에 전치 행렬을 행으로 정렬하여 저장*/
		int current = 1;
		for (int i = 0; i < S_a[0].col; i++) {
			for (int j = 1; j < number + 1; j++) {
				if (S_a[j].col == i) {
					/*전치행렬 만들기*/
					S_b[current].row = S_a[j].col;
					S_b[current].col = S_a[j].row;
					S_b[current].value = S_a[j].value;
					current += 1;
				}
			}
		}
	}
	return S_b;
}

void Print_Sparse_Mat(Element arr[]) {
	int row = arr[0].row;
	int col = arr[0].col;
	int no = arr[0].value;
	int current = 1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if ((arr[current].row == i) && (arr[current].col == j)) {
				printf("%d ", arr[current].value);
				current++;
			}
			else {
				printf("%d ", 0);
			}
		}
		printf("\\n");
	}

}

int main() {
	Element Sparse_A[Max_Element] = { {6,6,7}, {0,2,6}, {1,0,5}, {1,4,7}, {2,3,3}, {4,0,8}, {4,1,9}, {5,3,2} };
	Element* Spares_B = Transpose_Triple1(Sparse_A);
	Print_Sparse_Mat(Spares_B);
}

결과

과제에 대한 고찰

전에 했던 알고리즘은 다른 사람이 보았을 때 이해하기 쉽고 직관적이며 코딩하기도 쉬운편이다. 하지만 이번 알고리즘은 단순히 행과 열을 바꾸는 것이 아닌 0이라는 필요없는 정보는 빼고 행과 열그리고 0이 아닌 값의 개수를 저장하여 그것을 이용해 전치행렬을 만드는 것이다. 처음 이 문제에 대해서 생각 했을 때 행렬과 0이 아닌 값의 개수를 저장하는 다른 구조체 배열을 만들려고 했는데 이것을 배열[0]에다 저장하는 것을 보니 아직 알고리즘에 대해 공부를 더 해야겠다고 느꼈다. 이 것 말고는 전에 했던 1.2이 과제와 비슷해서 큰 고민을 안했던 것 같다.