알게 모르게 많이 쓰는 자료구조 배열. 배열은 같은 size를 가진 item을 메모리에 연속적으로 저장하는 구조입니다. 그렇기 때문에, k번째 원소를 가져오고 업데이트 하는 연산을 굉장히 빠르게 수행할 수 있어요. array에 관해서는 4편의 글을 쓸 예정이에요.
- 배열에 대해 알아봅시다. [현재 글]
- row major와 column major에 대해 알아봅시다. 링크
- 배열 주요 연산의 복잡도를 알아봅시다. 링크
- dynamic array에 대해 알아봅시다. 링크
이 글은 4개 중 1번째 글입니다.
먼저, 1차원 배열을 보겠습니다. array는 같은 size를 가진 item을 메모리에 연속적으로 저장한다고 했어요. 그렇다면, k번째 원소를 찾기 위해서는 시작 위치를 알면 됩니다.
제가 표시한 군청색 원소가 100에 있다고 해 보겠습니다. 그리고 하나의 원소는 크기가 8이라고 해 보겠습니다. 그렇다면, 다음 원소는 108에 있을 겁니다. 한 item이 8 만큼의 크기를 차지하기 때문입니다.
그러면, 11번째 원소의 위치는 어떻게 구하면 될까요? 이 역시 어렵지 않습니다. 1번째 원소는 위치 100에 있었습니다. 2번째 원소는 108에 있습니다. 11번째 원소는 1번째 원소로부터 10개 원소만큼 건너 뛰면 됩니다. 즉, 80만큼 이동하면 됩니다.
따라서, 위치 180에 11번째 원소가 있습니다. 여기까지 정리해 보겠습니다.
1차원 배열에서 1번째 원소의 위치가 S이고 item의 크기가 s일 때 k번째 원소의 위치는
S + (k-1)s
라고 할 수 있어요. 그냥 수식 한 번만 계산하면 되기 때문에, k번째 원소를 찾는 (index) 연산은 상당히 빠르게 수행할 수 있습니다. 기준 위치를 알고 있다면, 상대적인 위치 계산만 하면 되기 때문입니다. 상수 시간에 수행될 정도로 매우 빠릅니다.
상대적인 개념을 이용하면 ps를 할 때 자주 쓰이는 트릭도 이해하실 수 있습니다.
예제 1번 프로그램을 봅시다. 이 프로그램은 결과가 어떻게 나올까요?
arr은 원소 -2, -1, 0, 1, 2가 저장되어 있어요. int형을 가리키는 포인터는 arr의 3번째 원소를 가리키고 있어요. 즉 0을 가리키는 셈이지요. brr[-1]은 무엇을 의미할까요? brr은 int를 가리키는 포인터이므로, 현재 기준 위치인 군청색에서, 1칸만큼 뒤로 후퇴합니다.
그러면 -1을 보게 됩니다. 실행 결과도 -1이 출력될까요?
-1이 출력되는 것을 알 수 있습니다. 여기에서 핵심은 기준 위치를 바꾸었다는 점입니다. ps에서 심심치 않게 쓰이니 알아두시면 좋습니다.
2차원 배열은 어떨까요? 2차원 array는 array의 array라고 할 수 있어요. 그림으로 그려 봅시다.
arr은, arr[0], arr[1], arr[2] 등으로 갈 수 있는 정보를 담고 있어요. c, c++, java, python은 행 우선 방식을 쓰고 있어요. arr[10][10]에 있는 원소를 가져와 보겠습니다.
먼저, arr[10][10]으로 가기 위해, arr[10]에 접근해야 할 것입니다. 배열 arr의 한 원소 당 크기가 16이라고 해 봅시다. 우리는 arr의 시작 위치를 알고 있어요. 300이라 해 봅시다. 그러면, arr[10]의 위치는 300에 160을 더한 460이 될 겁니다.
arr[10]에는 배열 arr[10]으로 갈 수 있는 정보가 저장되어 있어요. 4000이라고 해 보겠습니다.
이제, arr[10]의 시작 위치에 접근하였어요. 행 우선 방식이라면, arr[10][0]입니다. 4000이네요. 이제, 배열 arr[10]에 있는 item의 크기가 8이라고 해 보겠습니다.
arr[10]의 시작 위치는 4000 이였습니다. arr[10]에 있는 원소의 크기는 8입니다. 따라서, arr[10][10]의 위치는 4000에 80을 더한 4080 이 됩니다. 여기까지 정리해 봅시다.
2차원 배열 arr[r][c]에 접근하기 위해
- arr[r]의 위치를 찾습니다.
- arr[r]에는 배열 arr[r]의 시작 주소를 가지고 있습니다.
- 이 정보를 가지고 arr[r][0]에 접근합니다.
- arr[r][0]의 위치와 배열 arr[r]에 들어있는 원소의 크기를 알고 있으니
- arr[r][c]의 위치를 찾을 수 있습니다.