다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 … | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
다음 그림과 같이 정방 행렬(square matrix)의 대각선 아래 모든 원소들의 값이 0인 행렬을 상삼각 행렬(upper triangular matrix)이라고 한다.

A[100][100]에 저장된 상삼각행렬을 기억 공간을 절약하기 위해서 0이 아닌 데이터만 일차원 배열 B[5050]에 저장하고자 한다. A[0][0]은 B[0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[90][93]은 B의 어느 위치에 저장되는가?
문제 이미지
1
B[4998]
2
B[4999]
3
B[5000]
4
B[5001]
해설

A[90][93]은 B[4998]에 저장된다.

상삼각행렬을 행 우선으로 저장하면 i행에는 열 i부터 99까지 100−i개의 원소가 있으므로, A[i][j]의 위치는 앞선 0~(i−1)행의 원소 수 합에 (j−i)를 더한 값이다.

∑k=089(100−k)=90×100−89×902=9000−4005=4995\sum_{k=0}^{89}(100-k) = 90 \times 100 - \dfrac{89 \times 90}{2} = 9000 - 4005 = 4995
4995+(93−90)=49984995 + (93 - 90) = 4998

  • B[4999]: 위치를 1부터 센 것처럼 하나를 더한 값이다.
  • B[5000]: 행 내부 오프셋 (j−i)=3 대신 다른 값을 더하는 등 위치 계산을 잘못한 값이다.
  • B[5001]: 앞선 행들의 원소 수 합 4995에 오프셋을 잘못 더한 값으로, 실제 위치보다 3칸 뒤이다.

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

이어서 풀어보기

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