2018 7급 국가직 기출풀이 - 자료구조론 마형 18번

문제 풀이에 앞서,

17번 문항은 저도 잘 설명할 수가 없어서 건너뜁니다T^T

---

문제

문18. 다음 5x5 희소 행렬(sparse matrix)을 구조체 배열로 표현하기 위해 <규칙>의 표현 규칙을 사용하여 <코드>의 C언어 코드를 작성하였다. <코드>의 ㉠에 들어갈 내용은? (단, 행렬의 행 번호와 열 번호는 0부터 시작한다)

< 코드 >

typedef struct {
    int row;
    int col;
    int val;
} term;
 
term A[] = __________㉠___________;
 

 

< 규칙 >

＊ 첫 번째 구조체인 A[0]의 row, col, val에는 희소 행렬의 행 개수, 열 개수, 값이 0이 아닌 원소 개수를 순서대로 저장한다. ＊두 번째부터의 나머지 구조체는 값이 0이 아닌 희소 행렬 원소를 표현하기 위해 사용되며, 각 구조체의 row, col, val에 해당 원소의 행 번호, 열 번호, ㄱ밧을 순서대로 저장한다. * 값이 0이 아닌 희소 행렬 원소 정보는 행 번호의 오름차순으로 구조체 배열 A에 저장되며, 행 번호가 같은 경우에는 오름차순으로 저장된다.

 

① { {4,4,4}, {0,1,5}, {0,2,2}, {1,3,1}, {3,0,3} }

② { {4,4,4}, {3,0,3}, {0,1,5}, {0,2,2}, {1,3,1} }

③ { {5,5,4}, {0,1,5}, {0,2,2}, {1,3,1}, {3,0,3} }

④ { {5,5,4}, {3,0,3}, {0,1,5}, {0,2,2}, {1,3,1} }

---

풀이전 참고

* 희소행렬(sparse matrix)

- 행렬의 값이 대부분 0인 경우를 가리키는 표현

- 개념적으로 희소성은 시스템들이 약하게 연결된 것에 해당한다. 한줄로 나열된 공과 공이 스프링으로 양 옆으로 하나씩 연기되었을 때 이것이 희소시스템이다.

- 그와 반대로 한 줄의 공들이 여러 방향의 공들과 스프링으로 연결되었을 때 이 시스템은 밀집 행렬(dense matrix)이 될 수 있다.

- 희소의 개념은 조합론과 네트워크 이론 등과 같은 응용분야에서 유용하다.

---

풀이과정

* 사실 이 문제에서는 이런 이론보다는 규칙을 잘 읽고 이해한 후 푸는 것이 중요하다!

 

1. A[0] = {5,5,4}

- 규칙1에 의하여...

- 5 *5 희소행렬

- 0이 아닌 원소의 개수는 4개

=> 여기서 정답이 3번 혹은 4번으로 갈린다.

 

2. A[1] = {0,1,5}

- 규칙3에 의해서 5값이 가장 먼저 입력된다.

- 규칙2에 의해서 0열의 1행의 값은 5이다.

 

3. 이후로는 규칙2를 따라 차례대로 입력한다.

A[2] = {0,2,2}

A[3] = {1,3,1}

A[4] = {3,0,3}

 

∴ ㉠ = A[] = { {5,5,4}, {0,1,5}, {0,2,2}, {1,3,1}, {3,0,3} }

---

마치며...

생각보다 준비기간이 길었던 포스팅이었네요.

모쪼록 도움이 되셨으면 좋겠습니다^^