값이 0인 원소들의 비율이 90%인 1,000 × 1,000 희소 행렬… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
값이 0인 원소들의 비율이 90%인 1,000 × 1,000 희소 행렬 표현에 관한 설명 중 옳은 것은?
1
2차원 배열로 모든 원소들을 표현하는 것이 저장 관점에서 효율적이다.
2
2차원 배열로 0이 아닌 원소들만 표현하기 위해서 1,000개의 저장 공간이 필요하다.
3
0이 아닌 원소들만 연결 리스트로 표현하는 것이 배열로 표현하는 것보다 전치행렬 연산에 효율적이다.
4
0이 아닌 원소들만 3원소쌍(행의 인덱스, 열의 인덱스, 값)으로 배열에 저장하는 것이 저장 관점에서 효율적이다.
해설

0이 아닌 원소만 3원소쌍 배열로 저장하는 방식이 저장 관점에서 효율적이다.

0이 아닌 원소는 106×0.1=10510^6\times 0.1=10^5개이므로, 3원소쌍으로 저장하면 약 3×1053\times 10^5칸으로 전체 10610^6칸보다 훨씬 적다.

  • 2차원 배열에 전 원소를 저장하는 설명: 90%를 차지하는 0까지 모두 저장해 공간 낭비가 크다.
  • 0이 아닌 원소에 1,000개 공간이 필요하다는 설명: 0이 아닌 원소는 100,000개이므로 맞지 않다.
  • 연결 리스트가 전치에 더 효율적이라는 설명: 3원소쌍 배열도 열별 개수로 위치를 정하는 빠른 전치로 효율적으로 처리할 수 있어 연결 리스트가 낫다고 단정할 수 없다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 07년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기