행렬 M=(a_{ij})가 |i-j| > 1 이면 0 값을 가질 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
행렬 M=(aij)M=(a_{ij})가 ∣i−j∣>1|i-j| > 1 이면 0 값을 가질 때, 이러한 행렬을 삼중대각행렬(tridiagonal matrix)이라고 하며, 다음은 6×66 \times 6 삼중대각행렬의 예를 보여준다. (단, 1≤i≤m1 \le i \le m, 1≤j≤n1 \le j \le n)
[a11a120000a21a22a230000a32a33a340000a43a44a450000a54a55a560000a65a66]\begin{bmatrix} a_{11} & a_{12} & 0 & 0 & 0 & 0 \\ a_{21} & a_{22} & a_{23} & 0 & 0 & 0 \\ 0 & a_{32} & a_{33} & a_{34} & 0 & 0 \\ 0 & 0 & a_{43} & a_{44} & a_{45} & 0 \\ 0 & 0 & 0 & a_{54} & a_{55} & a_{56} \\ 0 & 0 & 0 & 0 & a_{65} & a_{66} \end{bmatrix}
행렬 M(m×n)M(m \times n)의 0이 아닌 원소 aija_{ij}를 열 우선(column major) 순서로 배열 A에 저장한다고 할 때, 0이 아닌 원소 aija_{ij}가 배열 A에 저장되는 위치를 계산하는 수식으로 옳은 것은? (단, 배열 A의 시작주소는 α\alpha이고, 행렬 MM의 0인 원소는 배열에 저장하지 않는다)
1
α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)
2
α+3⋅(j−1)+(j−i)\alpha+3 \cdot (j-1)+(j-i)
3
α+3⋅(i−1)+(i−j)\alpha+3 \cdot (i-1)+(i-j)
4
α+3⋅(i−1)+(j−i)\alpha+3 \cdot (i-1)+(j-i)
해설

저장 위치 식은 α+3⋅(j−1)+(i−j)\alpha+3 \cdot (j-1)+(i-j)이며, 열 우선 순서에서 각 열의 0이 아닌 원소 개수로 구한다.

첫 열에는 원소가 2개, 나머지 열에는 3개씩 있으므로 j열 앞에 저장된 원소 수는 2+3(j−2)=3(j−1)−12+3(j-2)=3(j-1)-1이다. j열 안에서는 행 j-1, j, j+1 순으로 저장되어 열 안 오프셋이 i−j+1i-j+1이므로 위치는 α+3(j−1)−1+(i−j+1)=α+3(j−1)+(i−j)\alpha+3(j-1)-1+(i-j+1)=\alpha+3(j-1)+(i-j)이다.

검산: a11,a21,a12a_{11}, a_{21}, a_{12}의 위치가 각각 α,α+1,α+2\alpha, \alpha+1, \alpha+2로 맞는다.

  • 3⋅(j−1)+(j−i)3 \cdot (j-1)+(j-i)를 더하는 식: a21a_{21}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(i−j)3 \cdot (i-1)+(i-j)를 더하는 식: a12a_{12}의 위치가 α−1\alpha-1이 되어 성립하지 않는다.
  • 3⋅(i−1)+(j−i)3 \cdot (i-1)+(j-i)를 더하는 식: 행 우선 순서로 저장할 때의 위치 식이다.

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

이어서 풀어보기

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