# 배열 메모리 인덱싱, 주소 계산으로 O(1)이 되는 원리

- 게시: 2026.07.20
- 원문(HTML): https://trendbrief.news/articles/array-memory-indexing-o1-address-calculation.html
- 발행: [트렌드브리프](https://trendbrief.news/)

![배열 메모리 인덱싱, 주소 계산으로 O(1)이 되는 원리](https://trendbrief.news/assets/articles/%EB%B0%B0%EC%97%B4-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%9D%B8%EB%8D%B1%EC%8B%B1-%EC%A3%BC%EC%86%8C-%EA%B3%84%EC%82%B0%EC%9C%BC%EB%A1%9C-o-1-%EC%9D%B4-%EB%90%98%EB%8A%94-%EC%9B%90%EB%A6%AC/hero-auto.png)

> 배열이 arr[i]를 크기와 상관없이 상수 시간에 읽는 것은 원소를 연속 메모리에 두고 '시작 주소 + 인덱스 × 원소 크기'로 위치를 곧장 계산하기 때문이다. 인덱스가 0부터 시작하는 이유와 캐시 지역성, 언어별 차이를 원리로 정리한다.

배열에서 `arr[1000]`을 읽든 `arr[3]`을 읽든 걸리는 시간이 같은 이유는 단순하다. 배열은 원소를 메모리에 빈틈없이 연속으로 늘어놓고, 원하는 원소의 주소를 **시작 주소 + 인덱스 × 원소 한 개의 크기**라는 한 번의 곱셈·덧셈으로 곧장 계산하기 때문이다. 순서대로 훑을 필요가 없으니 어느 위치든 상수 시간(O(1), 입력 크기와 무관하게 일정한 시간)에 닿는다. 이 글은 C 언어 배열을 표준적으로 설명하는 cppreference와 파이썬 공식 문서를 근거로, 인덱싱이 실제로 어떻게 동작하는지, 왜 인덱스가 0부터 시작하는지, 연속 배치가 성능에 주는 이점을 원리 중심으로 다룬다. 동적 배열의 용량 확장 전략이나 언어별 세부 문법은 범위 밖이다.

## 인덱스는 어떻게 메모리 주소가 되나

배열의 시작 주소가 정해지면 나머지는 계산으로 끝난다. cppreference의 C 배열 문서 설명대로 배열 원소는 메모리에 연속으로 저장되므로, n번째 원소의 주소는 다음 공식으로 구한다.

**원소 주소 = 시작 주소 + (인덱스 × 원소 한 개의 크기)**

예를 들어 4바이트짜리 정수 배열이 주소 0x1000에서 시작한다면 `arr[0]`은 0x1000, `arr[1]`은 0x1004, `arr[3]`은 0x100C에 있다. 인덱스가 얼마든 곱셈 한 번과 덧셈 한 번이면 주소가 나오기 때문에, 배열 크기가 10이든 1,000만이든 접근 비용은 같다. 링크드 리스트처럼 앞 원소부터 포인터를 따라가야 하는 구조와 갈리는 지점이 바로 여기다.

C에서는 이 계산이 문법에 그대로 드러난다. `arr[i]`는 사실 "시작 주소에서 i칸 떨어진 곳의 값"을 뜻하는 포인터 산술의 축약형이다.

```
int arr[5] = {10, 20, 30, 40, 50};

int a = arr[3];  // 40
int b = *(arr + 3); // 40, arr[3]과 똑같은 계산
```

컴파일러는 `arr + 3`을 "시작 주소 + 3 × sizeof(int)"로 바꾼다. 인덱싱은 별도의 탐색이 아니라 주소 산술 그 자체인 셈이다.

## 왜 인덱스는 0부터 시작할까

인덱스가 시작 주소로부터 떨어진 거리, 곧 오프셋이기 때문이다. 첫 원소는 시작 주소에서 0칸 떨어져 있으니 오프셋이 0이고, 그래서 `arr[0]`이 첫 원소다. 앞의 공식에 대입하면 `arr[0]`의 주소는 "시작 주소 + 0 × 원소 크기", 즉 시작 주소 자신이 된다.

만약 인덱스를 1부터 셌다면 주소 공식이 매번 "시작 주소 + (인덱스 − 1) × 원소 크기"로 바뀌어 뺄셈이 한 번씩 더 붙는다. 0부터 세면 인덱스가 곧 오프셋이라 이 보정이 사라진다. 배열을 다루는 많은 언어가 0-기반 인덱싱을 쓰는 배경에는 이런 주소 계산의 단순함이 있다. 물론 포트란이나 루아처럼 1부터 세는 관례를 택한 언어도 있으니, 0-기반이 절대 규칙은 아니다.

![촘촘히 붙은 연속 셀 띠 위로 파란 화살표가 가운데 한 셀로 곧장 내려꽂히고, 시작점부터 그 셀까지 점선 구간이 표시된 선화 일러스트](https://trendbrief.news/assets/articles/%EB%B0%B0%EC%97%B4-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%9D%B8%EB%8D%B1%EC%8B%B1-%EC%A3%BC%EC%86%8C-%EA%B3%84%EC%82%B0%EC%9C%BC%EB%A1%9C-o-1-%EC%9D%B4-%EB%90%98%EB%8A%94-%EC%9B%90%EB%A6%AC/sec-ch1.jpg)

주소가 계산되니 어느 칸이든 한 번에 내려앉는다 — 연속 배치가 만드는 O(1) 임의 접근.

## 연속 배치가 캐시 지역성을 만든다

연속 메모리의 이점은 주소 계산의 단순함에서 그치지 않는다. CPU는 메모리에서 값 하나만 필요해도 그 주변을 **캐시 라인**(한 번에 읽어 오는 메모리 덩어리) 단위로 통째로 읽어 온다. 인텔 아키텍처에서 캐시 라인 크기는 보통 64바이트다. 4바이트 정수 배열이라면 한 번 읽을 때 인접한 16개가 함께 캐시에 올라온다는 뜻이다.

그래서 배열을 인덱스 순서대로 훑는 반복문은 캐시 적중률이 높다. 다음 원소가 이미 캐시에 올라와 있을 확률이 크기 때문이다. 이 성질을 공간 지역성(가까운 주소를 곧이어 쓸 가능성이 높다는 성질)이라 부르고, 배열이 성능이 중요한 코드에서 기본 자료구조로 쓰이는 이유이기도 하다. 반대로 메모리 여기저기를 무작위로 건너뛰며 접근하면 캐시가 매번 헛돌아 느려진다. 대규모 연산에서 메모리 접근 패턴이 실제 병목을 좌우한다는 점은 [메모리 병목을 줄이는 LLM 설계](https://trendbrief.news/articles/hardware-aware-llm-design-memory-bottlenecks.html)에서도 같은 원리로 다룬다.

2차원 배열도 결국은 1차원 연속 메모리에 눕는다. C를 비롯한 여러 언어는 행 우선(row-major) 순서, 즉 첫 행을 메모리에 쭉 깔고 그 뒤에 둘째 행을 잇는 방식으로 저장한다. cppreference의 C 배열 문서는 다차원 배열에서 가장 마지막 인덱스가 가장 빠르게 변한다고 설명한다. 그래서 중첩 반복문에서 안쪽 루프가 열(마지막 인덱스)을 훑도록 짜면 메모리를 연속으로 읽어 캐시 지역성을 살릴 수 있다. 같은 배열을 같은 횟수로 돌더라도 반복 순서를 바꾸면 속도가 크게 달라지는 이유다.

## 언어마다 배열의 실체가 다르다

지금까지의 설명은 원소 값이 메모리에 직접, 연속으로 박히는 C 스타일 배열을 전제로 한다. 모든 언어의 "배열"이 이렇게 동작하지는 않는다. [파이썬 공식 문서의 FAQ](https://docs.python.org/3/faq/design.html)는 CPython의 리스트가 링크드 리스트가 아니라 "다른 객체를 가리키는 참조(포인터)의 연속 배열"이라고 설명한다. 리스트 슬롯에는 값이 아니라 값이 있는 곳을 가리키는 포인터가 나란히 들어간다는 뜻이다.

그래서 파이썬 리스트도 인덱싱은 O(1)이다. 포인터 배열 위에서도 앞의 주소 공식이 그대로 통하기 때문이다. 다만 값이 메모리에 흩어져 있어, 값을 직접 이어 붙인 C 배열이나 넘파이 배열만큼의 캐시 지역성은 기대하기 어렵다. "배열 인덱싱은 O(1)"이라는 한 문장 뒤에는 이렇게 언어마다 다른 메모리 배치가 숨어 있다. 성능이 걸린 코드라면 인덱싱 비용뿐 아니라 값이 실제로 연속인지, 나아가 [인덱스 구조 자체의 메모리 사용량](https://trendbrief.news/articles/vector-search-index-memory-optimization.html)까지 함께 따져 봐야 한다.

## 관련 글

- [해시 테이블 충돌 체이닝, 버킷에 연결 리스트를 다는 방식](https://trendbrief.news/articles/hash-table-collision-chaining-explained.md)
- [그래프 탐색 BFS와 DFS, 큐와 스택으로 갈리는 선택 기준](https://trendbrief.news/articles/graph-traversal-bfs-vs-dfs.md)
- [이진 트리 순회와 높이, 재귀 깊이가 성능을 가르는 원리](https://trendbrief.news/articles/binary-tree-traversal-height-recursion-depth.md)
- [스택과 큐, LIFO·FIFO 차이와 실무 쓰임새](https://trendbrief.news/articles/stack-vs-queue-lifo-fifo-differences.md)
- [연결 리스트 자료구조, 노드와 포인터로 이해하기](https://trendbrief.news/articles/linked-list-data-structure-nodes-pointers.md)