---
title: "동적 배열: 빠른 인덱스 접근과 가끔 일어나는 복사의 대가"
author: "Lee"
published_at: "2026-10-21T06:20:04.935Z"
updated_at: "2026-09-30T09:27:01.354Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%8F%99%EC%A0%81-%EB%B0%B0%EC%97%B4-%EB%B9%A0%EB%A5%B8-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC%EA%B3%BC-%EA%B0%80%EB%81%94-%EC%9D%BC%EC%96%B4%EB%82%98%EB%8A%94-%EB%B3%B5%EC%82%AC%EC%9D%98-%EB%8C%80%EA%B0%80"
ai_assisted: false
---

# 동적 배열: 빠른 인덱스 접근과 가끔 일어나는 복사의 대가

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%8F%99%EC%A0%81-%EB%B0%B0%EC%97%B4-%EB%B9%A0%EB%A5%B8-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC%EA%B3%BC-%EA%B0%80%EB%81%94-%EC%9D%BC%EC%96%B4%EB%82%98%EB%8A%94-%EB%B3%B5%EC%82%AC%EC%9D%98-%EB%8C%80%EA%B0%80)

동적 배열은 연속된 메모리에 원소를 저장하면서 필요에 따라 저장 용량을 바꾸는 자료구조다. 논리적으로 들어 있는 원소 수인 길이와 실제 확보한 칸 수인 용량을 구분한다. 사용자는 크기가 늘어나는 배열처럼 보지만 내부에서는 다른 메모리 공간으로 옮기는 일이 일어난다.

![4칸짜리 배열을 8칸으로 복사하고 다섯 번째 값 50을 추가한 동적 배열](/api/v1/media/157e3cea-aca8-4dc0-8c91-7f010b4a639f)

*실제 원소 수인 크기와 확보된 저장 공간인 용량은 서로 다르다.*

### 인덱스가 주소가 되는 구조

고정 크기 원소의 시작 주소가 B, 원소 크기가 s이면 i번째 원소 주소는 B+i×s다. 따라서 유효 범위 검사와 주소 계산 후 바로 접근하여 O(1) 시간을 기대할 수 있다. 앞에서부터 i개 원소를 따라갈 필요가 없다. 연속 배치는 공간 지역성이 좋아 순회에도 유리하다.

용량이 남아 있을 때 끝에 원소를 추가하면 현재 길이 위치에 값을 쓰고 길이를 하나 늘린다. 길이 4, 용량 4인 상태에서 다섯 번째 원소를 넣으려면 새로운 공간이 필요하다. 용량 8을 확보하고 기존 네 원소를 복사한 뒤 새 값을 넣는 것이 전형적인 정책이다.

새 공간의 주소는 기존 공간과 다를 수 있다. 그래서 언어와 컨테이너 규약에 따라 원소를 가리키던 포인터, 참조, 반복자가 무효화될 수 있다. 크기 변화가 논리적 원소 수만 바꾸는 일이 아니라 저장 위치까지 바꿀 수 있다는 뜻이다.

### 작업별 비용은 다르다

인덱스 접근은 O(1)이지만 가운데 삽입은 뒤 원소를 밀어야 하므로 O(n)이다. 삭제도 순서를 유지하려면 남은 원소를 당겨야 한다. 순서를 버려도 되는 경우 마지막 원소로 빈칸을 채울 수 있으나, 그때는 자료구조의 관찰되는 동작이 바뀐다.

용량을 일정 비율로 늘리면 끝 추가의 분할 상환 비용은 O(1)이다. 개별 확장 한 번은 O(n)이라는 사실과 모순되지 않는다. 용량을 매번 한 칸만 늘리면 누적 복사량이 O(n²)이 되어 좋은 보장이 사라진다.

용량을 크게 늘리면 재할당 횟수는 줄고 사용하지 않는 메모리는 늘어난다. 반대로 너무 작게 늘리면 복사가 잦다. 원소 삭제 시 즉시 축소하지 않는 구현도 많으며, 축소 임계값을 분리하면 추가·삭제 반복으로 확장과 축소가 번갈아 발생하는 문제를 줄인다.

입력 크기를 예상할 수 있다면 미리 용량을 예약해 큰 복사를 줄일 수 있다. 많은 중간 삽입이 필요한 작업, 안정된 원소 주소가 중요한 작업에는 다른 구조가 나을 수 있다. 자료구조를 고를 때는 평균 조회 비용만큼 변경 위치와 메모리 이동을 함께 봐야 한다.

### 재할당을 드러낸 교육용 모형

```text
append(value):
    if length == capacity:
        new_capacity = max(1, capacity * 2)
        new_storage = allocate(new_capacity)
        for index in [0, length):
            new_storage[index] = old_storage[index]
        storage = new_storage
        capacity = new_capacity
    storage[length] = value
    length = length + 1
```

길이가 0이고 용량도 0인 초기 상태에서 단순히 두 배만 하면 계속 0이다. 최소 용량 1이라는 조건이 첫 추가를 가능하게 한다. 원소가 객체라면 여기서 복사하는 것이 객체 본체인지 참조인지도 언어의 컨테이너 의미에 따라 달라진다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Stacks and Queues](https://algs4.cs.princeton.edu/13stacks/)