0이 아닌 원소의 개수가 7개인 9 × 12 희소행렬에 대한 설명으로 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 24년 1회차

0이 아닌 원소의 개수가 7개인 9 × 12 희소행렬에 대한 설명으로 옳지 않은 것은?

행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하면, 108개의 배열 원소에 대한 공간이 필요하다.

0이 아닌 원소들에 대한 <행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현하면 14개의 배열 원소에 대한 공간이 필요하다.

행렬을 그대로 선형 순차 리스트로 표현하여 2차원 배열로 구현하는 것은 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어진다.

<행 번호, 열 번호, 값>의 쌍을 2차원 배열로 구현한 희소행렬에 대하여 전치 행렬을 구하는 방법의 시간 복잡도는 최악의 경우,  $O(\text{열의 수}^2 \times \text{행의 수})$ 이다.

해설

<행 번호, 열 번호, 값> 쌍 표현에 14개가 필요하다는 설명이 옳지 않다.

이 표현은 0이 아닌 원소 하나당 행 번호·열 번호·값 3개를 저장하므로 $7 \times 3 = 21$ 개가 필요하고, 행렬 크기·원소 수를 담는 머리 행까지 두면 24개가 된다. 14개는 원소당 2개만 센 값이다.

행렬을 그대로 2차원 배열로 두면 $9 \times 12 = 108$ 개 공간이 필요하다.
108개 중 7개만 0이 아니므로 대부분의 공간이 낭비되어 기억 공간 활용도가 떨어진다.
단순 전치 알고리즘은 열마다 모든 항을 훑어 열의 수 × 항의 수에 비례하고, 최악에는 항의 수가 행의 수 × 열의 수가 되므로 열의 수의 제곱 × 행의 수가 된다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기