> [!abstract] Introduction > 배열*Array*은 같은 타입의 원소들이 메모리에 빈틈없이 나란히 놓여 있는 가장 기본적인 자료구조입니다. 인덱스 하나로 어떤 원소든 바로 접근할 수 있다는 것이 가장 큰 강점이며, 거의 모든 프로그래밍 언어가 기본 문법으로 지원합니다. 이번 글에서는 배열에 대해 알아봅니다. ## 메모리 레이아웃 배열의 핵심은 **연속적인 메모리 배치**에 있다. 배열이 시작하는 메모리 주소를 기저 주소*base address*라 하면, 인덱스 $i$에 해당하는 원소의 주소는 다음과 같이 계산된다. $\text{addr}(A[i]) = \text{base} + i \times \text{sizeof}(\text{element})$ ![[arrayMemoryLayout.svg]] 이 산술 연산은 인덱스 $i$에 관계없이 항상 같은 시간이 걸린다. 배열이 $O(1)$의 시간복잡도를 가지는 임의 접근*random access*을 지원하는 이유가 바로 이것이다. 첫 번째 원소든 백만 번째 원소든, 한 번의 덧셈과 곱셈으로 주소를 구할 수 있다. C에서 배열을 선언하면 이 구조가 직접 드러난다. ```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*의 혜택을 받는다. 배열을 순회할 때 캐시 히트율이 높은 이유가 이 연속 배치 덕분이다[^cache-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$번째부터 마지막 원소까지 전부 한 칸씩 뒤로 밀어야 한다. 삭제도 마찬가지로, 빈 자리를 메우기 위해 뒤쪽 원소를 앞으로 당겨야 한다. ```python # 인덱스 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`가 모두 동적 배열이다. ![[dynamicArrayResize.svg]] 핵심 아이디어는 **용량을 두 배로 늘리는 전략**이다. 용량이 가득 찼을 때 기존 용량의 두 배를 가진 새 배열을 할당하고, $n$개의 원소를 모두 복사한다. 이 복사 과정의 시간복잡도는 $O(n)$이지만, 매번 일어나는 것이 아니라 용량이 찰 때만 발생한다. 상각 분석*amortized analysis*으로 보면, $n$번의 `append`에 소요되는 총 비용은 $O(n)$이므로, 개별 `append`의 상각 비용은 $O(1)$이다[^amortized-proof]. 간헐적으로 $O(n)$ 복사가 발생하더라도, 그 빈도가 기하급수적으로 줄어들어 평균적으로는 상수 시간을 유지하는 것이다. ```python # 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배 성장 공식[^cpython-growth]을 사용하여 메모리 낭비를 줄인다. ## 다차원 배열 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$칸씩 건너뛰어야 하므로 캐시 미스가 빈번해진다[^row-vs-col]. ## 배열과 다른 자료구조의 관계 배열은 다른 자료구조를 **구현**하는 가장 기본적인 재료다. [[Stack|스택]]은 배열의 끝에서만 삽입/삭제하면 자연스럽게 LIFO가 구현된다. Python의 `list`를 스택으로 쓸 때 `append()`와 `pop()`을 사용하는 것이 바로 이 패턴이다. [[Queue|큐]]의 원형 큐*circular queue* 구현은 배열 위에서 나머지 연산(`%`)으로 인덱스를 순환시켜 FIFO를 구현한다. [[Heap|힙]]은 완전 이진 트리를 배열 하나로 표현한 자료구조로, 부모-자식 관계를 인덱스 산술($\text{parent}(i) = \lfloor i/2 \rfloor$, $\text{left}(i) = 2i$, $\text{right}(i) = 2i + 1$)로 처리한다. [[Hashing|해시 테이블]]의 버킷 배열도 기본적으로 배열이다. 배열은 정렬 알고리즘의 주된 대상이기도 하다. Quick Sort, Merge Sort, Heap Sort 등 대부분의 정렬 알고리즘은 배열 위에서 동작하도록 설계되어 있다. 배열이 정렬되어 있으면 이진 탐색*binary search*으로 $O(\log n)$에 원소를 찾을 수 있다는 점도 배열의 중요한 특성이다. ## Python `list` Python의 `list`는 동적 배열이다. 내부적으로 객체에 대한 포인터 배열[^python-list-impl]을 유지하며, 용량이 부족하면 자동으로 크기를 늘린다. ```python 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]: 캐시 지역성(*cache locality*) — CPU 캐시가 인접한 메모리 주소를 미리 적재하는 특성. 배열은 원소가 연속된 메모리에 저장되어 캐시 히트율이 높지만, [[연결 리스트]]는 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다. [^amortized-proof]: 상각 분석 증명 — $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-growth]: CPython의 리스트 성장 공식 — `new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize`. 정확히 2배가 아닌, 약 12.5%씩 초과 할당하여 메모리 낭비를 줄인다. CPython 소스 `Objects/listobject.c:list_resize()` 참조. [^row-vs-col]: 행 우선 vs. 열 우선 순회 성능 — 행 우선 배치에서 `A[i][j]`를 $j$ 방향으로 순회하면 연속 메모리를 읽어 캐시 라인 하나로 여러 원소를 처리한다. 반면 $i$ 방향으로 순회하면 캐시 라인마다 한 원소만 사용하고 버리므로, 배열이 L1 캐시보다 클 때 성능 차이가 수 배에 달할 수 있다. [^python-list-impl]: CPython의 `list` 내부 구조 — `PyListObject`는 `ob_item`이라는 `PyObject **` 포인터 배열을 가진다. 각 원소가 객체를 가리키는 포인터이므로, C 배열처럼 값이 직접 연속 배치되지는 않는다. 이것이 NumPy `ndarray`와의 핵심 차이점이다. CPython 소스 `Include/cpython/listobject.h` 참조.