동적 배열

배열은 여러 값을 순서대로 저장하고 인덱스를 통해 특정 위치에 빠르게 접근할 수 있는 자료구조입니다.

우리가 보통 이야기하는 배열은 고정된 크기를 가진 연속된 공간에 값을 저장합니다. 그런데 만약 이러한 배열에 값을 계속 추가하고 싶다면 어떻게 해야할까요? 처음 설정한 공간이 가득 찼을 때 배열에 값을 계속 추가할 수는 없을까요?

JavaScript에서는 다음의 코드가 자연스럽게 동작합니다.

const numbers = [];

numbers.push(10);
numbers.push(20);
numbers.push(30);
numbers.push(40);

우리는 초기 선언시 배열에 별도의 크기를 정하지 않았으며 겉으로 보기에는 배열이 필요한 만큼 자동으로 늘어나는 것처럼 보입니다.

이처럼 필요할 때 내부 공간을 늘려 값을 계속 추가할 수 있게 만든 배열을 동적 배열(dynamic array) 이라고 합니다.

동적 배열이란

동적 배열(dynamic array) 은 고정된 크기의 배열을 사용하지만 공간이 부족해지면 더 큰 배열을 새로 만들어 기존 값을 복사해 옮기는 방식으로 동작하는 자료구조입니다.

겉으로는 다음처럼 보입니다.

const numbers = [];

numbers.push(10);
numbers.push(20);
numbers.push(30);
numbers.push(40);
numbers.push(50);

사용자는 크기를 고려하지 않고 push를 호출할 수 있습니다. 이때 내부에서는 다음과 같은 일이 일어납니다.

1. 아직 빈 칸이 있으면 그 칸에 값을 넣는다.
2. 빈 칸이 없으면 더 큰 배열을 새로 만든다.
3. 기존 값을 새 배열로 복사한다.
4. 새 값을 추가한다.

즉 동적 배열은 기존 배열을 계속 늘리는 것이 아니라 더 큰 배열로 변경하는 방식으로 크기 확장을 구현 합니다.

length와 capacity

동적 배열을 이해하려면 length와 capacity를 구분해야 합니다.

• length: 실제로 들어 있는 원소의 개수
• capacity: 내부 버퍼가 담을 수 있는 전체 칸의 수

예를 들어 배열에 값은 3개만 들어 있지만, 내부적으로는 6칸을 확보해두고 있을 수 있습니다.

length = 3
capacity = 6

index:   0    1    2    3    4    5
value:  10   20   30    _    _    _

사용자가 보는 배열의 길이는 3입니다. 하지만 내부에는 아직 세 칸의 여유 공간이 남아 있습니다.

이 여유 공간 덕분에 다음 push는 빠르게 처리할 수 있습니다.

push(40)

index:   0    1    2    3    4    5
value:  10   20   30   40    _    _

이 경우에는 기존 값을 옮길 필요가 없습니다. 비어 있는 다음 칸에 40을 넣고 length만 4로 늘리면 됩니다.

push가 일어날 때 내부 동작

동적 배열에서 push는 크게 두 가지 경우로 나눌 수 있습니다.

capacity가 남아 있을 때

내부 버퍼에 빈 칸이 남아 있다면 push는 단순합니다.

length = 3
capacity = 6

[10, 20, 30, _, _, _]
              ↑
             여기에 추가

push(40)을 하면 다음처럼 됩니다.

[10, 20, 30, 40, _, _]

이 경우에는 값을 하나 넣고 length를 하나 늘리면 됩니다. 따라서 시간복잡도는 O(1) 입니다.

capacity가 가득 찼을 때

문제는 내부 버퍼가 이미 가득 찬 경우입니다.

length = 4
capacity = 4

[10, 20, 30, 40]

여기에 push(50)을 하려면 새 칸이 필요합니다. 하지만 기존 배열 뒤에 바로 칸을 하나 더 붙일 수 있다는 보장은 없습니다.

그래서 동적 배열은 이를 위해 더 큰 버퍼를 새로 만듭니다.

과정을 코드가 아니라 동작으로 표현하면 다음과 같습니다.

1. 기존 배열이 가득 참
   [10, 20, 30, 40]

2. 더 큰 배열을 새로 만듦
   [_, _, _, _, _, _, _, _]

3. 기존 값을 새 배열로 복사
   [10, 20, 30, 40, _, _, _, _]

4. 새 값을 추가
   [10, 20, 30, 40, 50, _, _, _]

이 경우에는 기존 원소 4개를 모두 복사해야 합니다. 따라서 이 경우에는 시간복잡도가 O(n) 입니다.

배열을 복사하는 이유

동적 배열이 단순 확장이 아닌 기존 값을 복사하는 이유는 메모리의 연속성 때문입니다.

배열은 값들을 연속된 메모리 공간에 저장하기 때문에 인덱스로 빠르게 접근할 수 있습니다.

index:   0    1    2    3
value:  10   20   30   40

이런 구조 덕분에 numbers[2]에 접근할 때 앞에서부터 하나씩 확인하지 않을 수 있습니다. 배열의 시작 위치에서 일정한 거리만큼 이동해 바로 값을 읽을 수 있습니다.

이와 같이 기존 배열이 가득 찬 상태에서 값을 하나 더 추가하려면 새로운 다섯 번째 칸이 필요합니다. 문제는 기존 배열 바로 뒤의 메모리 공간이 비어 있다는 보장이 없다는 점입니다.

[10, 20, 30, 40][다른 데이터]

이 상태에서는 기존 배열 뒤에 새 칸을 붙일 수 없습니다. 배열의 연속성을 유지하려면 더 큰 연속 공간을 새로 확보해야 합니다.

새로운 더 큰 공간:

[_, _, _, _, _, _, _, _]

하지만 새 공간은 비어 있습니다. 따라서 기존 배열에 있던 값들을 새 공간으로 옮겨야 합니다.

[10, 20, 30, 40, _, _, _, _]

이렇게 복사하고 나면 새 배열도 이전 배열과 같은 순서를 유지합니다. 동시에 뒤쪽에 여유 공간이 생기기 때문에 다음 값을 추가할 수 있습니다.

이 복사 과정 때문에 resize가 일어나는 순간의 push는 O(n) 이 될 수 있습니다. 원소가 n개라면 새 배열로 옮겨야 하는 값도 n개이기 때문입니다.

배열의 사이즈를 늘리는 방법

동적 배열이 가득 찼을 때 새로운 공간은 얼마나 크게 만들어야 할까요?

가장 단순한 방법은 한 칸만 더 늘리는 것입니다.

capacity 4 → 5 → 6 → 7 → 8 ...

하지만 이 방식에는 문제가 있습니다. 매번 한 칸만 늘리면 새로운 값을 추가할 때마다 resize가 발생하게 됩니다. 그리고 이러한 resize 과정은 기존 원소를 모두 복사해야 하므로 많은 비용이 발생합니다.

그래서 동적 배열은 보통 더 큰 폭으로 capacity를 늘립니다.

capacity 4 → 8 → 16 → 32 ...

이렇게 2배씩 capacity를 늘리면 resize가 자주 일어나지 않습니다. 한 번 크게 늘려두면 그 뒤의 여러 번의 push는 남은 빈 칸을 사용해 빠르게 처리할 수 있습니다.

증가 방식	예시	특징
한 칸씩 증가	4 → 5 → 6 → 7	메모리는 아낄 수 있지만 resize가 너무 자주 일어난다.
고정 크기 증가	4 → 8 → 12 → 16	한 칸씩 늘리는 것보다는 낫지만 큰 입력에서 복사가 자주 발생한다.
비율로 증가	4 → 8 → 16 → 32	resize 횟수가 빠르게 줄어들어 push 비용을 분산하기 좋다.

동적 배열에서 push의 시간 복잡도

이제 동적 배열에서 push의 시간 복잡도를 다시 생각해봅시다.

동적 배열의 push에는 두 가지 상황이 있습니다.

상황	비용
capacity가 남아 있음	O(1)
capacity가 가득 차 resize 발생	O(n)

capacity가 남아 있는 일반적인 경우에는 기존 배열과 동일하게 O(1)입니다. 하지만 capacity가 가득 차 resize가 발생하는 순간에는 기존 원소를 모두 복사해야 하기 때문에 O(n)이 됩니다.

하지만 이러한 resize가 자주 발생하는 것은 아닙니다. capacity를 2배씩 늘린다고 가정할때 resize는 다음과 같이 점점 드물게 발생합니다.

capacity 1 → 2
capacity 2 → 4
capacity 4 → 8
capacity 8 → 16
capacity 16 → 32

처음에는 resize가 자주 발생하는 것처럼 보이지만 배열이 커질수록 다음 resize까지 더 많은 push를 처리할 수 있습니다.

대부분의 push: 빈 칸에 값 하나 추가 → O(1)
가끔의 push: 더 큰 배열 생성 + 기존 값 복사 → O(n)

이때 발생한 비싼 resize 비용을 그 사이의 많은 push들에 나누어 생각하다면 push 한 번당 평균적인 비용은 상수 시간에 가깝게 볼 수 있습니다.

이러한 분석을 분할 상환 분석(amortized analysis) 이라고 합니다. 그래서 동적 배열의 끝 삽입은 보통 amortized O(1) 이라고 표현합니다.

동적 배열의 장점

동적 배열의 가장 큰 장점은 배열의 사용성을 유지하면서도 끝에 값을 계속 추가할 수 있다는 점입니다.

인덱스 접근이 빠르다

동적 배열도 내부적으로는 배열 기반 구조입니다. 따라서 특정 위치를 알고 있다면 인덱스로 빠르게 접근할 수 있습니다.

const numbers = [10, 20, 30, 40];

numbers[2]; // 30

이런 접근은 기본 배열과 마찬가지로 O(1) 로 볼 수 있습니다.

끝 삽입이 효율적이다

동적 배열은 여유 capacity를 두기 때문에 대부분의 push를 빠르게 처리할 수 있습니다.

const numbers = [];

numbers.push(10);
numbers.push(20);
numbers.push(30);

끝에 계속 추가하는 작업이 많다면 동적 배열은 매우 실용적인 구조입니다.

사용하기 쉽다

사용자는 내부의 capacity나 resize를 직접 관리하지 않아도 됩니다. 그냥 배열처럼 사용하면 됩니다.

const messages = [];

messages.push("안녕하세요");
messages.push("반갑습니다");

내부적으로는 복잡한 일이 일어날 수 있지만 사용하는 입장에서는 단순한 배열 인터페이스를 유지할 수 있습니다.

동적 배열의 단점

동적 배열이 항상 좋은 것은 아닙니다.

resize 순간에는 비용이 발생한다

대부분의 push는 빠르지만 resize가 발생하는 순간에는 기존 값을 모두 복사해야 합니다.

[10, 20, 30, 40]

resize 후:

[10, 20, 30, 40, 50, _, _, _]

이 순간에는 O(n)의 비용이 발생할 수 있습니다. 그래서 매우 민감한 실시간 시스템에서는 이 일시적인 지연도 문제가 될 수 있습니다.

여유 공간 때문에 메모리를 더 사용할 수 있다

동적 배열은 다음 push를 빠르게 처리하기 위해 capacity를 보다 여유롭게 확보합니다. 따라서 실제 원소 수보다 더 많은 메모리를 사용할 수 있습니다.

length = 5
capacity = 8

[10, 20, 30, 40, 50, _, _, _]

빈 칸은 당장 사용되지 않는 공간이지만 메모리에는 확보되어 있습니다. 동적 배열은 시간을 아끼기 위해 어느 정도의 공간 낭비를 허용하는 구조입니다.

중간 삽입과 삭제는 여전히 느리다

동적 배열은 끝 삽입을 효율적으로 만들지만 중간 삽입과 삭제 문제를 해결하지는 않습니다.

[10, 20, 30, 40]

인덱스 1에 15 삽입:

[10, 15, 20, 30, 40]
          └── 뒤 원소들을 밀어야 함

중간에 값을 넣거나 삭제하면 여전히 원소를 이동시켜야 합니다. 따라서 중간 삽입과 삭제가 자주 일어나는 경우에는 연결 리스트 같은 다른 자료구조를 고려할 수 있습니다.

정리

동적 배열은 배열을 보다 유연하게 사용하기 위한 자료구조입니다. 내부 공간이 부족해지면 더 큰 배열을 새로 만들고 기존 값을 그곳으로 옮겨서 값을 계속 추가할 수 있게 합니다.

이 구조 덕분에 동적 배열은 배열의 장점인 빠른 인덱스 접근을 유지하면서도 값을 계속 추가할 수 있게 되었습니다. 다만 resize가 일어나는 순간에는 기존 값을 복사해야 하므로 일시적으로 O(n) 의 비용이 발생할 수 있습니다.

그래서 동적 배열의 push는 항상 O(1)은 아닙니다. 하지만 resize는 매번 일어나지 않고 한 번 여유 공간을 확보한 뒤에는 대부분의 push를 빠르게 처리할 수 있습니다. 이러한 이유로 동적 배열의 끝 삽입은 보통 amortized O(1) 이라고 표현합니다.