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

• 입력

  

• 출력

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

• 조건

  • 실습 과제 1에서 작성한 코드에 아래의 함수를 추가 구현
  • Element* Transpose_Triple2(Element S_a[]) 함수 구현

2.1의 알고리즘과는 다르게 이번에는 수행공간과 수행시간 모두를 고려한 알고리즘이다. 이것을 출족시키기 위해서는 우선 이차원 배열을 사용하지 않고 중첩 for을 사용해서는 안된다. 행과 열을 열과 행으로 바꾸는 과정에서 이중 for문을 사용하게 되는데 이것을 방지하기 위해서 정보를 어디에 저장할지 정하는 위치 정보를 미리 알 수 있다면 해결이 된다.

위의 표와 같이 row[]에 열의 개수 pos[]에 위치 정보를 저장해준다. 이때 pos[]를 구하는 법은 row[i] + pos[i] = pos[i+1]이다.

#include <stdio.h>
#include <stdlib.h>

#define Max_Element 8

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

Element* Transpose_Triple2(Element S_a[]) {
	static Element S_b[Max_Element];
	int number = S_a[0].value;
	/*row와 pos에 S_a[0].col만큼 배열의 크기를 할당*/
	int* row = (int*)malloc(sizeof(int) * S_a[0].col);
	int* pos = (int*)malloc(sizeof(int) * S_a[0].col);
	S_b[0].value = number;
	S_b[0].row = S_a[0].row;
	S_b[0].col = S_a[0].col;
	if (number > 0) {
		/*row를 S_a[0].col개수만큼 0으로 초기화*/
		for (int i = 0; i < S_a[0].col; i++) {
			row[i] = 0;
		}
		/*S_a[].col의 개수를 저장*/
		for (int i = 1; i < number + 1; i++) {
			row[S_a[i].col] += 1;
		}
		pos[0] = 1;
		/*위치 정보를 저장*/
		for (int i = 1; i < S_a[0].col; i++) {
			pos[i] = pos[i - 1] + row[i - 1];
		}
		/*S_b배열 만들기*/
		for (int i = 1; i < number + 1; i++) {
			int temp = pos[S_a[i].col];
			pos[S_a[i].col] += 1;
			S_b[temp].row = S_a[i].col;
			S_b[temp].col = S_a[i].row;
			S_b[temp].value = S_a[i].value;
		}
	}
	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_Triple2(Sparse_A);
	Print_Sparse_Mat(Spares_B);
}

결과

과제에 대한 고찰

이번 과제는 수행시간 수행공간을 모두 고려한 효율적인 알고리즘을 짜는 코드였다. 원래 작성코드에서 계속 생각하고 다듬고를 반복해서 결국은 수행시간과 수행공간 모드를 고려한 코드가 나왔다는 것이 인상적이였다. 처음에 이 문제를 풀 때 2차원 배열을 어떻게 1차원 배열로 만들 수 있을까 하고 고민해보았고 값과 그 값이 들어가야하는 위치를 1차원 배열로 받아보자고 생각했지만 공간 복잡도가 다시 올라갔다. 그 후 강의자료를 통해서 pos[i+1] = pos[i] + row[i]를 사용한다는 것을 알게되었고 그후 수행시간 수행공간을 모두 고려한 알고리즘을 짤 수 있었다. 보통 배열 문제가 나오면 이차원 배열을 항상 사용했는데 이런식으로 다르게 생각해서 1차원 배열로 문제를 풀 수 있다는 것이 신기했다. 특히 pos[]를 이용한다는 것은 생각하지도 못했던 방법이였다. 앞으로도 다양한 알고리즘문제를 풀어보고 익히면서 그 문제에는 어떤 알고리즘을 적용해야하는지 생각해봐야겠다.