이건 1번문제

1.void transpose(term a[][], term b[][]){
2.
3.int m, n, v, i, j, p;
4. m = a[0][0]; //희소 행렬 a의 행 수
5. n = a[0][1]; //희소 행렬 a의 열 수
6. v = a[0][2]; //희소 행렬 a에서 0이 아닌 원소 수
7. b[0][0]=n; // 전치 행렬 b의 행 수
8. b[0][1]=m; // 전치 행렬 b의 열 수
9. b[0][2]=v; // 전치 행렬 b의 원소 수

10. if( v > 0){ // 0이 아닌 원소가 있는 경우에만 전치 연산 수행
11.
12. p=1;
13.  for( i=0 ; i<n ; i++) // 희소 행렬 a의 열 별로 전치 반복 수행

14.  for( j=1; j<=v ; j++) //0이 아닌 원소 수에 대해서만 반복 수행

15.   if(a[j][i] == i) { //현재의 열에 속하는 원소가 있으면 b[]에 삽입

16.     b[p][0] = a[j][1]
17.     b[p][1] = a[j][0]
18.    b[p][2] = a[j][2]
19.     p++;
20     
21.     }
22.     }
23.}

이 소스는   a라는 테이블과 b라는 테이블을 두고,
0번과 1번에는 행과 열을, 2에는 원소값을 두는거임.
즉

  a                    b
-----            -----
2 6 2     ->>    6 2 2
0 2 1              0 2 1
0 4 3              4 0 3

이런식으로 바꾼다는 소스임
밑에 2번문제도 마찬가지고. 단지 방법이 틀릴뿐.

그럼. 공간복잡도를 보면,
알고리즘을 실행시키는데 무관한 부분과 밀접한 부분으로 나눔.
무관한 부분은 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 등이 이에 포함.

밀접한 부분은 변수를 저장하기 위한 공간이 필요함. 순환스택도 필요하다는데 이 소스는 스택은 관련없으니 패쓰

그럼 공간복잡도로 풀어보면 10라인은 (n+1) , 12라인은 1, 13,14라인은 합치면 2n 15는(n+1) 16~18라인은 3n, 19는 1
여기까지 풀어보면 공간복잡도는 6n+2
시간복잡도는 Big-O로 O(n)

------------------------------------------------------------------
이건 2번문제
1.void fastTranspose(term a[][], term b[][]) {

2.int col_term[MAX_COL] = {0}; // 각 열의 원소 개수를 저장하는 배열
3.int starting_pos[MAX_COL]; // 각 열의 위치를 저장하는 배열
4.int i, j, m, n, v;
5.m = a[0][0];
6. n = a[0][1]; //열의 크기
7. v = a[0][2]; // 원소의 개수
8. b[0][0]=n;
9. b[0][1]=m;
10. b[0][2]=v;
11. if(v > 0) {
12. for( i=1 ; i <= v; i++) // 각 열의 원소 개수 구하기
13.  col_term[a[i][1]]++;
14. starting_pos[0] = 1; // 0열의 시작 위치를 초기화

15. for( i=1 ; i < n ; i++) // 각 열의 위치를 구하기
16. starting_pos[i] = starting_pos[i-1] + col_term[i-1];
17.  j= starting_pos[a[i][1]]; // 배열 a에서 b로 옮기기
18.   b[p][0] = a[j][1]
19.   b[p][1] = a[j][0]
20.   b[p][2] = a[j][2]
21.   starting pos[a[i][1]]++;
22.  }
23. }
}

얘도 풀어서 보면, 공간복잡도는 2n+10
시간복잡도는 O(n)


음 왠지 풀어보니까 아닌거 같은데 ㅡ_ㅡ
맞나 안맞나 확인좀 해줘 횽들!
길어서 미안해 ㅠㅠ