▷ An,a의 밴드 안에 있는 원소 수는 얼마인가?
(풀이) 정방 밴드 행렬은 주대각선을 기준으로 하위와 상위 행렬 원소의 개수가 동일하다. 그러므로 주대각선의
원소 n 과 한측면의 원소의 수에 2배를 한 결과의 합이 정방 밴드 행렬 원소의 개수를 구하는 식이라 할 수 있다.
▷ An,a의 밴드 안에 있는 원소 ai,j에서 i와j는 어떤 관계인가?
(풀이) i는 밴드 행렬에서 행값을 나타내고 j는 행렬의 열값을 나타낸다. 이때 i와j간에 차는 주대각선과의 거리를
나타낸다고 생각할 수가 있다. 즉 |i-j|는 주대각선과의 거리를 표현하는 식이 된다. 이 때 i>j 이면 주대각선보다
하위에 위치하고 있는 원소이고, i<j 이면 주대각선의 상위에 위치하고 있는 원소이다.
▷ 최하위 대각선으로부터 시작해서An,a의 밴드가 배열 b에 순차적으로 저장된다고 가정하자. 이러한 경우 An,a의
하위밴드에 있는 원소 aij 의 위치에 대한 주소를 구하는 공식을 작성하라.
(풀이) 하위밴드에 속한 원소의 위치를 구하는 방법은 전체원소의 개수를 구하는 식의 변형으로 얻어질 수 있다.
하위원소들의 대각선 순서대로 일차원 배열에 저장이 되므로, 이것의 주소값은 해당 원소가 몇 번째로 저장이
되었는지를 구하는 것과 같다고 할 수가 있다. 그러므로 하위밴드에 속한 원소들의 전체 개수에서 저장이 되지 않은
원소의 개수를 제거한 후 위치하는 j를 더하면 해당원소의 주소값을 알아낼수가 있다.
- 제 1 판 2.8 추가 연습문제 8번
▷ 일반화된 밴드 행렬 An,a,b란 0이 아닌 모든 항이 주 대각선 아래의 a-1개의 대각선, 주 대각선, 주 대각선
위의 b-1개의 대각선으로 구성되는 밴드 안에 있는 n*n행렬이다.
▷ An,a,b의 밴드 안에 있는 원소 수는 얼마인가?
(풀이) 정방 밴드 행렬의 원소의 수를 구하는 방법과 차이는 없다. 단, 상위와 하위 밴드의 원소의 개수가 서로
다르므로, 각각 구하여 합을 내어야 한다. 유도되는 식은 다음과 같다.
▷ An,a,b의 밴드 안에 있는 원소 ai,j에서 i와j는 어떤 관계인가?
(풀이) 일반화된 밴드 행렬 역시 정방 밴드 행렬과 i와j간의 관계는 다르지 않다. 즉 |i-j|는 주대각선과의 거리를
표현하는 식이 된다. 이 때 i>j 이면 주대각선보다 하위에 위치하고 있는 원소이고, i<j 이면 주대각선의 상위에
위치하고 있는 원소이다. 만약 i=j 라면 주대각선상에 존재하는 원소이다.
▷ 1차원 배열 c에 An,a,b의 밴드를 순차적으로 표현하라. 이 표현에서 행렬 An,a,b에 있는 원소 aij의 값을 결정하는
알고리즘을 기술하라.
(풀이) 1차원 배열의 c에 저장되는 순서를 밴드 행렬의 하위부터 순서대로 저장한다고 할 때 각각의 주소값은 정방 밴드행렬과 다르지 않다. 그러므로 하위행렬을 구하는 식은 다음과 같다.
위와 같은 방법으로 주대각선상의 원소의 저장주소는 이마 하위행렬이 저장이 완료된 후이므로 하위행렬 총
원소의 개수에 j 만큼을 더해주면 주소가 구해지게 된다.
상위 밴드 행렬의 주소값을 구하는 식은 이미 지나온 하위행렬의 개수와 주대각선 원소의 수를 합한 결과에
현재까지 저장된 상위행렬의 개수에 행값을 나타내는 I를 더하여주면 구할 수 있다.
위의 식들로 이용하여 이미 하위행렬부터 대각선순으로 저장된 일반화된 밴드 행렬의 위치를 찾아가는 알고리즘은 다음과 같이 간단하게 설명 할 수 있다.
Ⅰ. 행렬에 index flag 는 i와j를 비교한다.
Ⅱ. i와j 의 비교를 마치면 i,j의 크기에 따라서 해당하는 주소를 계산한다.
Ⅲ. 계산된 배열의 주소로 element flag를 이동하여 해당값을 return한다.
