n \times n 하삼각 행렬은 총 n(n+1)/2개의 원소를 갖는다… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
n×nn \times n 하삼각 행렬은 총 n(n+1)/2n(n+1)/2개의 원소를 갖는다. 원소 aija_{ij}(1≦i≦j≦1 \leqq i \leqq j \leqq n)가 최소 공간을 사용하도록 1차원 배열 b[k]b[k]에 행우선순서(row-major order)로 저장했을 때, 하삼각 행렬의 원소 aija_{ij}가 저장될 배열 b[k]b[k]의 색인 kk를 계산하는 식으로 옳은 것은? (단, ii는 행 색인 값, jj는 열 색인 값으로 하고, 1차원 배열 bb에는 하삼각 행렬의 0 값은 저장되지 않으며, bb의 색인 kk의 값은 0부터 시작한다)
정방 행렬(square matrix) 중에서 대각선보다 위의 모든 원소가 0인 경우를 특별히 하삼각 행렬(lower triangular matrix)이라 하며, 다음은 4×44 \times 4 하삼각 행렬의 예이다. (단, aija_{ij}는 0이 아닌 어떤 실수 값을 의미하고, 0은 반드시 0이어야 함을 의미한다)
[a11000a21a2200a31a32a330a41a42a43a44]\begin{bmatrix} a_{11} & 0 & 0 & 0 \\ a_{21} & a_{22} & 0 & 0 \\ a_{31} & a_{32} & a_{33} & 0 \\ a_{41} & a_{42} & a_{43} & a_{44} \end{bmatrix}
1
(i−1)×n+(j−1)(i-1) \times n + (j-1)
2
j×(j−1)/2+(i−1)j \times (j-1)/2 + (i-1)
3
i×(i−1)/2+(j−1)i \times (i-1)/2 + (j-1)
4
(j−1)×n+(i−1)(j-1) \times n + (i-1)
해설

행우선으로 저장할 때 원소 aija_{ij}의 색인은 k=i(i−1)/2+(j−1)k = i(i-1)/2 + (j-1)이다.

하삼각 행렬의 r행에는 0이 아닌 원소가 r개 있으므로, i행 앞의 행들에 저장된 원소 수는 1+2+⋯+(i−1)=i(i−1)/21+2+\dots+(i-1) = i(i-1)/2이다.
i행 안에서 aija_{ij} 앞에는 j−1j-1개의 원소가 있고 색인이 0부터 시작하므로 두 값을 더한 것이 k가 된다.

예를 들어 a32a_{32}는 3⋅2/2+1=43 \cdot 2/2 + 1 = 4로, a11,a21,a22,a31a_{11}, a_{21}, a_{22}, a_{31} 다음 위치에 저장된다.

  • (i−1)×n+(j−1)(i-1) \times n + (j-1)은 0까지 모두 저장하는 일반 정방 행렬의 행우선 색인이다.
  • (j−1)×n+(i−1)(j-1) \times n + (i-1)은 일반 정방 행렬의 열우선 색인이다.
  • j(j−1)/2+(i−1)j(j-1)/2 + (i-1)은 상삼각 행렬을 열우선으로 저장할 때의 식으로, 하삼각 행렬의 행우선 저장에는 맞지 않는다.

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

이어서 풀어보기

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