[C로 쓴 자료구조] 삼각행렬 배열의 주소 계산

아래와 같이 정방행렬의 대각선 위 또는 아래 모든 원소들의 값이 0인 행렬을 각각 하삼각 행렬, 상삼각 행렬이라고 한다. A[n][n]에 저장된 삼각 행렬을 메모리를 절약하기 위해서 0이 아닌 데이터만을 일차원 배열 B[n(n+1)/2]에 저장하고자 한다. A[0][0]은 B[0][0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[i][j]는 B의 어느 위치에 저장되는가? 단 각각 하삼각 행렬의 i,j 는 i >=j 이고, 상삼각 행렬의 i,j 는 i <=j 이다.

 

하삼각 행렬

 

 

 

 

 

상삼각 행렬

 

 

위의 문제들은 등차 수열의 합 공식을 사용해 풀 수 있다. 상삼각 행렬, 하삼각 행렬과 문제에 따라

시작 값 a, 더하는 행의 수 n, 등차 d를 대입하여 풀 수 있다.

등차수열의 합 공식