핵심 인사이트 (3줄 요약)
- 본질: 배열 (Array)은 동일 타입 원소를 연속된 메모리 블록에 저장하여, 인덱스 하나로 임의의 위치를 O(1)에 접근하는 가장 단순하고 빠른 선형 자료구조다.
- 가치: CPU 캐시 라인이 연속 메모리를 한 번에 로드하므로, 순차 탐색 시 캐시 히트율이 극도로 높아 실질 성능이 연결 리스트를 압도한다.
- 판단 포인트: 크기가 고정되고 읽기·순회가 빈번하면 배열, 삽입·삭제가 많거나 크기가 가변적이면 동적 배열(ArrayList)이나 연결 리스트를 선택한다.
Ⅰ. 개요 및 필요성
배열은 컴퓨터 메모리의 물리적 특성—주소 연산이 O(1)—을 그대로 활용한 원시 자료구조다. 배열의 시작 주소 base와 원소 크기 size를 알면, i번째 원소 주소는 base + i × size로 즉시 계산된다. 포인터 추적 없이 단 한 번의 산술 연산이므로 **랜덤 접근 (Random Access)이 O(1)**이다.
배열의 시간 복잡도
| 연산 | 배열(정적) | 동적 배열 |
|---|---|---|
| 접근 (index) | O(1) | O(1) |
| 탐색 (선형) | O(n) | O(n) |
| 삽입 (끝) | — | O(1) 분할상환 |
| 삽입 (중간) | O(n) | O(n) |
| 삭제 (끝) | — | O(1) |
| 삭제 (중간) | O(n) | O(n) |
정적 배열(C의 int arr[100])은 스택 또는 힙에 고정 크기로 할당된다. 동적 배열 (Dynamic Array, Java ArrayList, C++ vector, Python list)은 용량 초과 시 2배 크기로 재할당(Doubling)하여 삽입 n번의 분할상환 비용을 O(1)로 유지한다.
📢 섹션 요약 비유: 배열은 아파트 각 호실에 같은 크기 물건을 하나씩 넣은 것—호수(인덱스)만 알면 엘리베이터 없이 바로 가는 구조다.
Ⅱ. 아키텍처 및 핵심 원리
메모리 레이아웃
base address = 0x1000, sizeof(int) = 4
┌──────┬──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ ← 원소 값
├──────┼──────┼──────┼──────┼──────┤
│0x1000│0x1004│0x1008│0x100C│0x1010│ ← 주소
└──────┴──────┴──────┴──────┴──────┘
[0] [1] [2] [3] [4]
접근: arr[3] = *(base + 3×4) = *(0x100C) = 40 → O(1)
다차원 배열: 행 우선 vs 열 우선
2차원 배열 A[R][C]에서 원소 A[i][j]의 물리 주소는:
- 행 우선 (Row-Major):
base + (i×C + j) × size— C, C++, Java - 열 우선 (Column-Major):
base + (j×R + i) × size— Fortran, MATLAB, NumPy 기본
행렬 곱셈에서 열 우선 배열의 두 번째 피연산자를 전치(Transpose)하면 캐시 효율이 크게 오른다.
캐시 지역성 (Cache Locality)
현대 CPU는 데이터를 64바이트 단위의 캐시 라인 (Cache Line) 으로 로드한다. 배열 원소는 연속 메모리이므로 arr[0] 접근 시 arr[0]~arr[15](int 기준)가 L1 캐시에 한꺼번에 올라온다. 순차 순회 시 캐시 미스가 거의 없어 연결 리스트 대비 2~10배 빠른 실측 성능을 보인다.
동적 배열 성장 전략
초기 capacity = 1
삽입마다 size 초과 시 capacity × 2 재할당
[1]→[1,2]→[1,2,3,4]→[1..8]→...
분할상환 분석:
n번 삽입 총 복사 횟수 = 1+2+4+...+n < 2n → O(1) amortized
📢 섹션 요약 비유: 동적 배열은 방이 꽉 차면 두 배 큰 집으로 이사하는 전략—이삿짐이 가끔 많지만, 평균적으로는 한 번에 조금씩 옮기는 셈이다.
Ⅲ. 비교 및 연결
배열 vs 연결 리스트 vs 해시 테이블
| 항목 | 배열 | 연결 리스트 | 해시 테이블 |
|---|---|---|---|
| 접근 | O(1) 인덱스 | O(n) | O(1) 평균 |
| 삽입(끝) | O(1) amort | O(1) | O(1) 평균 |
| 삽입(중간) | O(n) | O(1) 포인터 | — |
| 메모리 연속성 | ✅ 연속 | ❌ 분산 | 부분 연속 |
| 캐시 효율 | ✅ 최고 | ❌ 낮음 | 중간 |
| 크기 유연성 | 정적 고정 | 동적 | 동적 |
📢 섹션 요약 비유: 배열은 칠판에 번호 순서대로 적은 리스트, 연결 리스트는 각 메모장에 "다음은 저 서랍"이라고 적은 보물지도다.
Ⅳ. 실무 적용 및 기술사 판단
주요 활용 사례
- 버퍼 관리 (Buffer Management): 네트워크 패킷, I/O 버퍼, 링 버퍼(원형 배열)
- 행렬 연산 (Matrix Operations): 그래픽스 변환, 딥러닝 가중치 텐서, BLAS 라이브러리
- 힙·세그먼트 트리: 완전 이진 트리를 배열로 표현 (
parent = (i-1)/2,left = 2i+1) - 슬라이딩 윈도우: 연속 구간 최솟값/최댓값 처리 (인덱스 산술 활용)
기술사 판단 기준
읽기/순회 위주 + 크기 예측 가능 → 정적 배열 또는 ArrayList
삽입/삭제 빈번 + 순서 중요 → 연결 리스트
키-값 매핑 + 순서 불필요 → 해시 테이블
정렬된 범위 쿼리 → 트리맵 or 세그먼트 트리
📢 섹션 요약 비유: 도서관 책장에 번호로 꽂힌 책(배열)은 "23번 책"을 바로 꺼낼 수 있지만, 중간에 새 책을 끼우려면 나머지를 한 칸씩 밀어야 한다.
Ⅴ. 기대효과 및 결론
배열은 자료구조의 '원점'이다. 인덱스 기반 O(1) 접근과 캐시 친화적 메모리 레이아웃 덕분에, 힙·해시 테이블·세그먼트 트리 등 고급 자료구조의 내부 구현이 모두 배열 위에 얹힌다. 한계는 삽입·삭제 시 원소 이동 비용(O(n))과 연속 메모리 확보 제약이다. 동적 배열은 더블링 전략으로 공간 낭비를 최대 2배로 제한하면서 분할상환 O(1) 삽입을 달성한다.
결론: 성능 최우선·순서 접근 패턴에는 배열이 최적이며, 삽입·삭제 중심·가변 크기 시나리오에는 동적 배열 또는 연결 리스트로 전환을 고려한다.
📌 관련 개념 맵
| 개념 | 관계 |
|---|---|
| 동적 배열 (Dynamic Array) | 배열 + 더블링 전략 |
| 연결 리스트 (Linked List) | 연속성 없는 대안, 삽입 O(1) |
| 힙 (Heap) | 배열로 구현하는 완전 이진 트리 |
| 해시 테이블 (Hash Table) | 배열 버킷 + 해시 함수 |
| 세그먼트 트리 (Segment Tree) | 배열 기반 구간 쿼리 |
| 슬라이딩 윈도우 (Sliding Window) | 배열 인덱스 산술 기법 |
📈 관련 키워드 및 발전 흐름도
[동적 배열 (Dynamic Array)]
│
▼
[연결 리스트 (Linked List)]
│
▼
[힙 (Heap)]
│
▼
[해시 테이블 (Hash Table)]
이 흐름도는 선행 개념이 현재 개념으로 응축되고, 다시 확장 개념으로 이어지는 순서를 보여준다.
👶 어린이를 위한 3줄 비유 설명
- 배열은 번호가 적힌 서랍장이야. 3번 서랍을 열고 싶으면 바로 3번으로 가면 돼.
- 서랍이 꽉 차면 두 배 큰 서랍장으로 이사 가는 게 동적 배열이야.
- 중간 서랍에 새 물건을 끼우려면 뒤 서랍을 다 한 칸씩 밀어야 해서 시간이 오래 걸려.