배열 행 우선 순위, 열 우선 순위

2차원 배열에 어떠한 값들을 저장하는 방법은 두 가지가 있습니다.

두 가지 방법으로 저장한 배열은 각각 '행 우선 배열'과 '열 우선 배열'이라고 부릅니다.

하나씩 알아보도록 하겠습니다.

 

---

행 우선 배열(row major ordering)

행 우선 배열 (row major ordering)

먼저 행우선 배열입니다. 이름 그대로 행을 우선시해서 저장하는 배열을 뜻합니다.

위의 그림에서 각 행들에 속하는 요소들을 빨간색 네모로 묶어보았는데 저 빨간색 네모를 먼저 채우고 다음 네모를 채운다고 생각하시면 됩니다.

즉, 1행을 다 채우고 2행을 채우는 식으로 배열을 채워나갑니다.

 

요소의 순서

그런 식으로 배열을 채워나가면 저장되는 요소들의 순서는 위의 그림과 같습니다.

 

 

요소의 주소

 

요소의 주소

이제 요소들의 주소를 알아보겠습니다.
일단 axb 배열의 (i,j)의 주소를 구하는 공식은 '시작 주소 + ((i-1) * b + (j-1)) * 요소의 크기' 입니다.
즉 위의 시작주소가 100이고 요소의 크기가 4인 4x5 배열에서 (2,3)의 주소는
'100 + ((2-1) * 5 + (3-1)) * 4 = 128'입니다.

어떻게 저렇게 되는지 알아보겠습니다.
일단 (2,3)의 배열은 시작 주소에서 1행의 5개의 요소와 2행에서 2개의 요소를 지난 뒤 있습니다.
여기서 1행의 5개의 요소는 (2-1) * 5 즉, (i-1) * b 에서 구할 수 있습니다.
그리고 2행의 2개의 요소는 (3-1) 즉, (j-1)에서 구할 수 있습니다.
그런데 저희가 구하려고 하는 것은 요소의 주소이므로 이 5개의 요소가 배열에서 차지하는 크기를 구해야 합니다. 그러므로 이때동안 구한 요소의 개수에 요소의 크기(*4)를 곱해줍니다. 그리고 배열의 시작 주소를 더해주면(+100) '((2-1) * 5 + (3-1)) * 4 + 100 = 128'이 나오게 됩니다.
위의 그림에서는 요소의 크기를 미리 곱해주고 더해준 그림을 뜻합니다. 결과는 같습니다.

 

---

열 우선 배열(column major ordering)

열 우선 배열 (column major ordering)

다음은 열 우선 배열입니다. 이는 열을 우선시해서 저장하는 배열을 뜻합니다.
앞에서 설명한 행 우선 배열과 유사합니다. 차이점은 행이 열이 된 것 밖에 없습니다.
행 우선 방식에서는 1행에 해당하는 요소들을 모두 채우고 2행을 채운다고 하면 열 우선 방식에서는 1열에 해당하는 요소(1행 1열, 2행 1열, 3행 1열, 4행 1열)을 모두 채운 뒤 2열(1행 1열, 2행 1열, 3행 2열, 4행 2열)을 채우는 식으로 배열을 채워나갑니다.

요소의 순서

열 우선 방식으로 배열을 채워나가면 배열에 저장되는 요소들의 순서는 위와 같습니다.

요소의 주소

이제 열 우선 방식에서의 요소들의 주소를 알아보겠습니다.
axb 배열의 (i,j)의 주소를 구하는 공식은 '시작 주소 + ((j-1) * a + (i-1)) * 요소의 크기' 입니다.
j와 a, i를 파란색으로 표현하였는데 행 우선 배열에서 다른 부분을 뜻합니다. 다른 점은 i와 j 자리가 바뀌었고 b가 a가 되었습니다.
예를 들어서 보면 시작주소가 100이고 요소의 크기가 4인 4x5 배열에서 (2,3)의 주소는
'100 + ((3-1) * 4 + (2-1)) * 4 = 136'입니다.

 

요소의 주소

이제 요소들의 주소를 알아보겠습니다.
일단 axb 배열의 (i,j)의 주소를 구하는 공식은 '시작 주소 + ((j-1) * a + (i-1)) * 요소의 크기' 입니다.
즉 위의 시작주소가 100이고 요소의 크기가 4인 4x5 배열에서 (2,3)의 주소는
'100 + ((3-1) * 4 + (2-1)) * 4 = 136'입니다.

어떻게 저렇게 되는지 알아보겠습니다.
일단 (2,3)의 배열은 시작 주소에서 1, 2행의 8개의 요소와 3행의 1개의 요소를 지난 뒤 있습니다.
여기서 1,2 행의 8개 요소는 (3-1) * 4 즉, (j-1) * a 에서 구할 수 있습니다.
그리고 3행의 1개 요소는 (2-1) 즉, (i-1)에서 구할 수 있습니다.
그런데 저희가 구하려고 하는 것은 요소의 주소이므로 이 9개의 요소가 배열에서 차지하는 크기를 구해야 합니다. 그러므로 이때동안 구한 요소의 개수에 요소의 크기(*4)를 곱해줍니다. 그리고 배열의 시작 주소를 더해주면(+100) '((3-1) * 4 + (2-1)) * 4 + 100 = 136'이 나오게 됩니다.
위의 그림에서는 요소의 크기를 미리 곱해주고 더해준 그림을 뜻합니다. 결과는 같습니다.

---

 

간단하게 행과 열의 크기를 입력받으면 행 우선 배열과 열 우선 배열에서 요소가 어떤 순서로 저장되는지 보여주는 소스코드를 작성해 보았습니다. 참고해주세요^^

소스코드 : https://gist.github.com/fpdjsns/e19458808dbe31869106e5c42346dd11

row major ordering & column major ordering

 

실행결과