c언어 2차원 배열 : 메모리 상에 어떻게 저장이 될까요?

 C언어에서 2차원 배열은, 어떻게 메모리 상에 저장이 될까요? 오늘은 이 부분만 집중적으로 보도록 하겠습니다. 먼저, int형 배열인, arr[3][4]를 선언하였습니다. 그러면 메모리 상에 어떻게 생성이 될까요? 일단 행렬로 치면, 3행 4열이라고 볼 수는 있는데요.

 

 & 연산자를 쓰면, 현재 주솟값을 볼 수 있는데요. 예제 프로그램을 보면서 이해를 해 보도록 합시다.

 

 

---

 먼저, 예제 1을 봅시다.

 

 

 3행 4열의 배열을 선언하였습니다. 그리고 2중 for loop를 돌면서, 저는 i와 j와 arr[i][j]의 주솟값을 출력하고 있습니다. 그러면 어떻게 결과가 나올까요?

 

 

 위와 같이 나오는데요. arr[0][0], arr[0][1], arr[0][2], arr[0][3], arr[1][0], ... 순으로 주솟값이 증가함을 볼 수 있어요. 그리고 그 간격 또한 일정하다는 것을 볼 수 있는데요. 이를 메모리 상에 다시 그려보면 아래와 같습니다.

 

 

 즉, 배열의 base 주소를 addr이라고 하면, arr[0][0]의 주소는 base가 됩니다. arr[0][1]의 주소를 구하려면, base에 배열에 있는 원소의 크기만큼 더하면 될 거에요. arr[1][1]의 주소를 구하려면요?

 

 

 먼저 한 행당 열이 몇 개 있나요? 4개 있습니다. 그러면 arr[1]의 주소로 가기 위해서 원소의 크기에다가, 4를 곱한 값을 더할 겁니다. 다음에, arr[1]의 address를 알아냈습니다. 이를 bp라고 합시다. 그러면 1행 1열로 가야 되는데요. 이것은 arr[1]로부터 1칸만을 더 가면 됩니다. 따라서, bp에서 원소 크기만큼 또 더하면 될 겁니다. int brr[3][2]짜리 배열에서는 어떨까요?

 

 

 brr은 이런 식으로 메모리에 할당이 될 겁니다. 그러면 여기에서 brr[2][1]에 접근을 하려면 어떻게 해야 할까요? 우리는, brr의 원소가 차지하는 byte 수랑 한 행당 가지고 있는 열의 길이만 알고 있습니다.

 

 

 일단, brr[2]의 주소를 어떻게 계산할까요? 한 행당, 2개의 열을 가지고 있어요. brr[2]는 3번째 행이므로, 2개의 행은 뛰어야 합니다. 따라서, 2개의 열에 건너뛴 행의 갯수인 2에다가, 원소 하나 당 차지하고 있는 byte 수를 base에 더해야 합니다. 그러면 brr[2]의 address가 나올 겁니다. 이를 bp라 합시다.

 

 

 그 다음에, 1번째 열을 찾아 가야 하는데요. 이는 기준점에서, 1칸 만큼 이동한 겁니다. 따라서, bp에 원소 크기만큼을 더해야 합니다. 그러면 brr[2][1]에 접근할 수 있습니다. 이를 일반화 시켜 봅시다.

 

 

 r행 c열의 2차원 배열 brr이 있습니다. 저는 crr[i][j]에 접근하려고 해요. address는 어떻게 얻어올까요? 먼저, brr[0]의 주소를 base라고 하면, brr[i]를 얻어와야 합니다. 한 행당 c개의 열이 있으니까, brr[i]의 address는 base + c*i*한 원소당 차지하는 크기로 구할 수 있습니다.

 

 다음에, brr[i][0]으로부터 몇 칸을 이동해야 하나요? j칸만 이동하면 됩니다. 따라서, brr[i]의 addr에, j*한 원소당 차지하는 크기를 더하면, brr[i][j]의 주소가 나옵니다. 이를 통해서, brr[i][j]에 접근할 수 있어요.

 

 

 이제, 조금 중요할 수 있는 이야기를 해 보겠습니다.

 

 

---

 원소 하나만큼 볼 때 1 단위만큼 이동한다고 해 봅시다. 배열 arr이, r행 c열일 때, arr[i][j]를 탐색하기 위해서, arr[0][0]으로부터, ir + c 단위만큼 이동해야 접근이 가능했습니다.

 

 

 이를 다시 그림으로 그려보면 아래와 같이 그릴 수 있습니다.

 

 

 즉, 2차원 array가 배열 상에서 저장이 될 때, 제가 화살표를 친 순서대로 저장이 되었어요. 보면, 행이 작으면 낮은 주소에 저장이 되었습니다. 이를 Row major order이라고 합니다. C언어에서는 이러한 방식으로 저장이 됩니다. 반대로, 아래와 같이 저장이 될 수도 있어요.

 

 

 이 때에는 열이 작으면 열이 큰 것보다 낮은 주소에 저장됩니다. 열이 같다면 행이 작은 게 더 낮은 address에 저장이 되고 있어요. 이 방식을 Column major order이라고 합니다. 그러면 i행 j열에 접근하기 위해서, j*c+i 단위만큼 이동하면 될 거에요. 베이스로부터요.자료 구조 시간에 다시 언급을 하겠지만, 이 구조를 잘 이해하는 것은 굉장히 중요해요. dp 테이블을 만들 때에도, 이러한 특성을 잘 이용해야, 더 효율적으로 작동되는 프로그램을 만들 수 있기 때문이에요.