n \times n 하삼각 행렬은 총 n(n+1)/2개의 원소를 갖는다… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
하삼각 행렬은 총 개의 원소를 갖는다. 원소 ( n)가 최소 공간을 사용하도록 1차원 배열 에 행우선순서(row-major order)로 저장했을 때, 하삼각 행렬의 원소 가 저장될 배열 의 색인 를 계산하는 식으로 옳은 것은? (단, 는 행 색인 값, 는 열 색인 값으로 하고, 1차원 배열 에는 하삼각 행렬의 0 값은 저장되지 않으며, 의 색인 의 값은 0부터 시작한다)정방 행렬(square matrix) 중에서 대각선보다 위의 모든 원소가 0인 경우를 특별히 하삼각 행렬(lower triangular matrix)이라 하며, 다음은 하삼각 행렬의 예이다. (단, 는 0이 아닌 어떤 실수 값을 의미하고, 0은 반드시 0이어야 함을 의미한다)
1
2
3
4
해설
행우선으로 저장할 때 원소 의 색인은 이다.
하삼각 행렬의 r행에는 0이 아닌 원소가 r개 있으므로, i행 앞의 행들에 저장된 원소 수는 이다.
i행 안에서 앞에는 개의 원소가 있고 색인이 0부터 시작하므로 두 값을 더한 것이 k가 된다.예를 들어 는 로, 다음 위치에 저장된다.
- 은 0까지 모두 저장하는 일반 정방 행렬의 행우선 색인이다.
- 은 일반 정방 행렬의 열우선 색인이다.
- 은 상삼각 행렬을 열우선으로 저장할 때의 식으로, 하삼각 행렬의 행우선 저장에는 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요