배열의 메모리 구조

3 min read

배열의 메모리 구조

연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조

핵심 개념

연속된 메모리 할당

메모리 주소:  1000   1004   1008   1012   1016
            +------+------+------+------+------+
배열 arr:   |  10  |  20  |  30  |  40  |  50  |
            +------+------+------+------+------+
인덱스:        [0]    [1]    [2]    [3]    [4]
  • 배열의 모든 요소는 연속된 메모리 공간에 저장된다
  • 각 요소는 동일한 크기의 메모리를 차지한다

인덱스를 통한 O(1) 접근

요소의 주소 = 시작 주소 + (인덱스 × 요소 크기)

arr[3]의 주소 = 1000 + (3 × 4) = 1012
  • 인덱스만 알면 단 한 번의 계산으로 해당 요소에 접근 가능
  • 이것이 배열의 가장 큰 장점: Random Access O(1)

코드 예시

Java

int[] arr = new int[5];  // 연속된 20바이트 할당 (4바이트 × 5)
arr[0] = 10;
arr[3] = 40;  // O(1) - 바로 접근

C

int arr[5];
int* ptr = arr;          // 배열의 시작 주소
int third = *(ptr + 2);  // arr[2]와 동일, 포인터 연산

메모리 레이아웃 상세

1차원 배열

int arr[4] = {1, 2, 3, 4};

Stack Memory:
+------+------+------+------+
|   1  |   2  |   3  |   4  |
+------+------+------+------+
  arr    arr+1  arr+2  arr+3

2차원 배열 (Row-Major Order)

int matrix[2][3] = {{1,2,3}, {4,5,6}};

메모리 배치 (행 우선):
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
[0,0][0,1][0,2][1,0][1,1][1,2]

matrix[i][j]의 주소 = base + (i × 열개수 + j) × 요소크기

캐시 친화성 (Cache Locality)

배열은 캐시 히트율이 높다:

CPU가 arr[0]을 읽을 때:
1. arr[0]~arr[N]이 캐시 라인에 함께 로드됨
2. 이후 arr[1], arr[2]... 접근 시 캐시에서 바로 읽음
3. 연결리스트 대비 실제 성능이 훨씬 좋음

면접 포인트

  1. 왜 O(1) 접근이 가능한가?

    • 연속된 메모리 + 동일한 요소 크기 → 주소 계산 공식

  2. 배열의 메모리 할당 위치는?

    • 지역 변수 배열: 스택
    • 동적 할당 (new, malloc): 힙

  3. 2차원 배열 순회 시 왜 행 우선이 빠른가?

    • 메모리가 행 우선으로 저장되므로 캐시 히트율이 높음

  4. 배열의 단점은?

    • 크기 고정 (정적 배열)
    • 삽입/삭제 시 요소 이동 필요 O(n)

Backlinks