배열

Introduction

배열Array은 같은 타입의 원소들이 메모리에 빈틈없이 나란히 놓여 있는 가장 기본적인 자료구조입니다. 인덱스 하나로 어떤 원소든 바로 접근할 수 있다는 것이 가장 큰 강점이며, 거의 모든 프로그래밍 언어가 기본 문법으로 지원합니다. 이번 글에서는 배열에 대해 알아봅니다.

메모리 레이아웃

배열의 핵심은 연속적인 메모리 배치에 있다. 배열이 시작하는 메모리 주소를 기저 주소base address라 하면, 인덱스 $i$ 에 해당하는 원소의 주소는 다음과 같이 계산된다.

$\text{addr}(A[i]) = \text{base} + i \times \text{sizeof}(\text{element})$

이 산술 연산은 인덱스 $i$ 에 관계없이 항상 같은 시간이 걸린다. 배열이 $O(1)$ 의 시간복잡도를 가지는 임의 접근random access을 지원하는 이유가 바로 이것이다. 첫 번째 원소든 백만 번째 원소든, 한 번의 덧셈과 곱셈으로 주소를 구할 수 있다.

C에서 배열을 선언하면 이 구조가 직접 드러난다.

int arr[5] = {10, 20, 30, 40, 50};
// arr[0]의 주소가 0x1000이고 sizeof(int) == 4라면:
// arr[0] → 0x1000
// arr[1] → 0x1004
// arr[2] → 0x1008
// arr[3] → 0x100C
// arr[4] → 0x1010

원소들이 연속적으로 배치되어 있기 때문에 CPU 캐시가 인접한 데이터를 미리 적재하는 공간 지역성spatial locality의 혜택을 받는다. 배열을 순회할 때 캐시 히트율이 높은 이유가 이 연속 배치 덕분이다¹.

핵심 연산과 시간 복잡도

연산	시간 복잡도	설명
접근 (`A[i]`)	$O(1)$	주소 산술로 바로 접근
탐색 (비정렬)	$O(n)$	처음부터 순회
탐색 (정렬)	$O(\log n)$	이진 탐색binary search 가능
끝 삽입	$O(1)$ *	동적 배열의 상각 시간
임의 위치 삽입	$O(n)$	뒤쪽 원소를 한 칸씩 이동
임의 위치 삭제	$O(n)$	뒤쪽 원소를 한 칸씩 이동

* 동적 배열 기준, 상각 분석amortized analysis

접근이 $O(1)$ 인 것은 위에서 설명한 주소 계산 방식 덕분이다. 삽입과 삭제가 $O(n)$ 인 이유는 원소들의 연속 배치를 유지해야 하기 때문이다. 인덱스 $k$ 에 원소를 삽입하면, $k$ 번째부터 마지막 원소까지 전부 한 칸씩 뒤로 밀어야 한다. 삭제도 마찬가지로, 빈 자리를 메우기 위해 뒤쪽 원소를 앞으로 당겨야 한다.

# 인덱스 2에 99를 삽입하면
# [10, 20, 30, 40, 50]
#           ↓ 30, 40, 50을 한 칸씩 뒤로
# [10, 20, 99, 30, 40, 50]

이 비용은 연결 리스트와 정반대다. 연결 리스트는 삽입/삭제가 $O(1)$ (노드 참조가 있을 때)이지만 접근이 $O(n)$ 이고, 배열은 접근이 $O(1)$ 이지만 삽입/삭제가 $O(n)$ 이다.

정적 배열과 동적 배열

정적 배열

정적 배열static array은 크기가 컴파일 시점에 결정되어 변경할 수 없다. C의 int arr[100]이 대표적이다. 크기를 넘어서는 원소를 추가할 수 없고, 미리 최대 크기를 예측해야 하는 부담이 있다.

동적 배열

동적 배열dynamic array은 원소가 가득 차면 더 큰 배열을 새로 할당하고 기존 원소를 복사하여 크기를 늘린다. Python의 list, Java의 ArrayList, C++의 std::vector가 모두 동적 배열이다.

핵심 아이디어는 용량을 두 배로 늘리는 전략이다. 용량이 가득 찼을 때 기존 용량의 두 배를 가진 새 배열을 할당하고, $n$ 개의 원소를 모두 복사한다. 이 복사 과정의 시간복잡도는 $O(n)$ 이지만, 매번 일어나는 것이 아니라 용량이 찰 때만 발생한다.

상각 분석amortized analysis으로 보면, $n$ 번의 append에 소요되는 총 비용은 $O(n)$ 이므로, 개별 append의 상각 비용은 $O(1)$ 이다². 간헐적으로 $O(n)$ 복사가 발생하더라도, 그 빈도가 기하급수적으로 줄어들어 평균적으로는 상수 시간을 유지하는 것이다.

# Python list의 동적 크기 조정 확인
import sys

lst = []
prev_size = 0
for i in range(20):
    lst.append(i)
    curr_size = sys.getsizeof(lst)
    if curr_size != prev_size:
        print(f"len={len(lst):2d}  capacity변경  {prev_size}→{curr_size} bytes")
        prev_size = curr_size

CPython의 list는 정확히 2배가 아닌, 약 1.125배 성장 공식³을 사용하여 메모리 낭비를 줄인다.

다차원 배열

2차원 이상의 배열은 행렬matrix, 이미지 픽셀, 게임 보드 등을 표현할 때 쓰인다. 논리적으로는 행과 열의 격자지만, 물리적 메모리는 1차원이므로 원소를 일렬로 펼치는 방법이 필요하다.

행 우선row-major 배치는 같은 행의 원소를 연속으로 배치한다. C, Python(NumPy 기본값), Rust가 이 방식을 따른다. $m \times n$ 배열에서 원소 $A[i][j]$ 의 주소는 다음과 같다.

$\text{addr}(A[i][j]) = \text{base} + (i \times n + j) \times \text{sizeof}(\text{element})$

열 우선column-major 배치는 같은 열의 원소를 연속으로 배치한다. Fortran, MATLAB, Julia가 이 방식을 따른다.

$\text{addr}(A[i][j]) = \text{base} + (j \times m + i) \times \text{sizeof}(\text{element})$

이 차이는 성능에 직접적인 영향을 미친다. 행 우선 배치에서 행 방향으로 순회하면 연속된 메모리를 읽으므로 캐시 히트율이 높지만, 열 방향으로 순회하면 매번 $n$ 칸씩 건너뛰어야 하므로 캐시 미스가 빈번해진다⁴.

배열과 다른 자료구조의 관계

배열은 다른 자료구조를 구현하는 가장 기본적인 재료다.

스택은 배열의 끝에서만 삽입/삭제하면 자연스럽게 LIFO가 구현된다. Python의 list를 스택으로 쓸 때 append()와 pop()을 사용하는 것이 바로 이 패턴이다. 큐의 원형 큐circular queue 구현은 배열 위에서 나머지 연산(%)으로 인덱스를 순환시켜 FIFO를 구현한다. 힙은 완전 이진 트리를 배열 하나로 표현한 자료구조로, 부모-자식 관계를 인덱스 산술( $\text{parent}(i) = \lfloor i/2 \rfloor$ , $\text{left}(i) = 2i$ , $\text{right}(i) = 2i + 1$ )로 처리한다. 해시 테이블의 버킷 배열도 기본적으로 배열이다.

배열은 정렬 알고리즘의 주된 대상이기도 하다. Quick Sort, Merge Sort, Heap Sort 등 대부분의 정렬 알고리즘은 배열 위에서 동작하도록 설계되어 있다. 배열이 정렬되어 있으면 이진 탐색binary search으로 $O(\log n)$ 에 원소를 찾을 수 있다는 점도 배열의 중요한 특성이다.

Python `list`

Python의 list는 동적 배열이다. 내부적으로 객체에 대한 포인터 배열⁵을 유지하며, 용량이 부족하면 자동으로 크기를 늘린다.

arr = [10, 20, 30, 40, 50]

# O(1) 접근
print(arr[3])          # 40

# O(1) 상각 끝 삽입
arr.append(60)         # [10, 20, 30, 40, 50, 60]

# O(n) 임의 위치 삽입
arr.insert(2, 99)      # [10, 20, 99, 30, 40, 50, 60]

# O(n) 탐색
idx = arr.index(40)    # 4

# 슬라이싱 — O(k), k는 슬라이스 길이
sub = arr[1:4]         # [20, 99, 30]

list는 범용적이지만, 수치 계산에는 NumPy의 ndarray가 적합하다. ndarray는 같은 타입의 원소를 포인터 없이 직접 연속 배치하여, 메모리 효율과 벡터 연산 성능이 list보다 월등히 높다.

출처

Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press.
Kamran, A. (2022) 전문가를 위한 C (박지윤, Trans.; 1st edn). 한빛미디어.
Python Software Foundation (2025) Data Structures — More on Lists. Available at: https://docs.python.org/3/tutorial/datastructures.html.

캐시 지역성(cache locality) — CPU 캐시가 인접한 메모리 주소를 미리 적재하는 특성. 배열은 원소가 연속된 메모리에 저장되어 캐시 히트율이 높지만, 연결 리스트는 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다. ↩
상각 분석 증명 — $n$ 번의 append에서 복사가 일어나는 횟수는 용량이 1, 2, 4, 8, …, $n$ 일 때이다. 총 복사 비용은 $1 + 2 + 4 + \cdots + n = 2n - 1 = O(n)$ 이므로, append 한 번당 상각 비용은 $O(n)/n = O(1)$ 이다. Cormen et al. (2022), Chapter 16.3 참조. ↩
CPython의 리스트 성장 공식 — new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize. 정확히 2배가 아닌, 약 12.5%씩 초과 할당하여 메모리 낭비를 줄인다. CPython 소스 Objects/listobject.c:list_resize() 참조. ↩
행 우선 vs. 열 우선 순회 성능 — 행 우선 배치에서 A[i][j]를 $j$ 방향으로 순회하면 연속 메모리를 읽어 캐시 라인 하나로 여러 원소를 처리한다. 반면 $i$ 방향으로 순회하면 캐시 라인마다 한 원소만 사용하고 버리므로, 배열이 L1 캐시보다 클 때 성능 차이가 수 배에 달할 수 있다. ↩
CPython의 list 내부 구조 — PyListObject는 ob_item이라는 PyObject ** 포인터 배열을 가진다. 각 원소가 객체를 가리키는 포인터이므로, C 배열처럼 값이 직접 연속 배치되지는 않는다. 이것이 NumPy ndarray와의 핵심 차이점이다. CPython 소스 Include/cpython/listobject.h 참조. ↩