<사고력 훈련 문제 #6>: 삼각행렬의 원소의 주소를 구하기

# 삼각행렬의 원소의 주소를 구하는 문제

---

문제) 정방행렬의 대각선 위나 아래의 모든 원소들이 0일 때 그 행렬을 삼각행렬(triangular matrix)이라 한다. 아래의 그림은 하삼각행렬(lower triangular matrix)과 상삼각행렬(upper triangular matrix)을 나타낸다. 

 $n$개의 행을 가진 하삼각행렬에서 0이 아닌 $i$행의 원소는 최대   $i + 1$개 이다. 따라서 0이 아닌 항의 총계는 다음과 같다. // $i$는 0부터 시작한다. 하삼각행렬의 0번째 행의 원소의 개수는 1개이고, 그 아래의 행을 따라가면서 원소의 개수를 세면 도출 가능한 규칙이다. 

$d =$$\sum_{i=0}^{n-1} {i+1}$$=$$\frac{n(n+1)} {2}$ // $d$는 distance라는 의미에서 붙인 이름이다. 실제로 인덱스를 계산할 때 이만큼의 거리를 먼저 더한 후 열에 해당하는 값을 더해주는 연산을 적용하면 쉽게 인덱스를 구할 수 있다.

 이차원 배열로 삼각 행렬을 저장하는 것은 기억 장소를 낭비하기 때문에 삼각행렬에서 0이 아닌 원소들만을 저장하는 방법이 필요하다. 행렬의 원소를 배열   $b[n(n+1)/2-1]$에 저장시키고   $a[0][0]$은   $b[0]$에, 다른 원소는 행 우선순서로 저장시킨다고 할 때 원소   $a_{ij}$의 주소를 계산하는 수식을 구하라.

# 풀이

---

 일차원 배열에 저장하는 방식인데, 결국 인덱스 값만 바르게 들어가면 되는 것이다. 행과 열을 적절한 수식으로 변환하여 순서대로 일차원 배열에 입력한다고 생각했을 때 이 수식을 구하는 방법을 생각해보자.

<하삼각행렬>

$d =$$\sum_{i=0}^{n-1} {i+1}$$=$$\frac{n(n+1)} {2}$ 이므로  $a[i][j] = b$ $[$  $\sum_{i=0}^{n-1} {i+1}$$=$$\frac{n(n+1)} {2}$ $]$  이다.

<상삼각행렬>

 $d =$  총 개수 - 0의 개수 + 열로 구할 수 있다. // 삼각행렬 그림을 살펴보자. 어떤 규칙성이 있을까? 찾아보면, 행이 1씩 증가할 때마다 0의 개수가 1씩 증가하는 규칙이 있다. 이 규칙을 토대로하면, 한 행이 꽉 차 있는 상황을 먼저 고정한 후에 0의 갯수만 가변값을 가지게끔 수식을 준 후 열에 해당하는 수만 더하면 인덱스($d$ )에 접근이 가능하다.

 위에서 추론을 통해 가정한 식을 그대로 구현해보면, $d$는 아래와 같다.

 $d$ =

$ni -$  $\sum_{i=1}^{i} {i}$  $+j$ // 이 식에서 $n$은 정방행렬의 행 혹은 열의 개수를 뜻한다. 즉, 한 행당 $n$개의 원소가 있는 것이라 생각하면 된다. 0의 개수를 나타내는 $i$는 가변인자이고, 행을 의미한다. 0행에서의 0의 개수는 0개이고, 1행에서의 개수는 1개다. 하나씩 증가하는 규칙을 바탕으로 $i$에 대한 시그마(sum)가 도출된다고 생각하면 이해가 잘 될 것이다.

=  $\frac{2ni - i^2 + i} {2}$ $+j$

$a[i][j] =$  $b$ $[$  $\frac{2i(n - i + 1)} {2}$ $+j$ $]$ 이다.