동적 배열
1. 개요
동적 배열은 배열과 유사하게 요소에 순차적으로 접근할 수 있으며, 필요에 따라 크기를 동적으로 조절할 수 있는 자료 구조이다. 배열의 장점을 유지하면서도, 요소의 추가 및 삭제 연산을 효율적으로 처리할 수 있도록 설계되었다. 동적 배열은 크기 조정에 따른 성능 저하를 상쇄하기 위해, 일반적으로 공간을 미리 확보하는 방식으로 구현되며, 다양한 프로그래밍 언어에서 지원된다.
| 자료 구조 유형 | 배열 |
|---|---|
| 접근 | Θ(1) |
| 탐색 | Θ(n) |
| 삽입 | Θ(n) |
| 삭제 | Θ(n) |
| 공간 복잡도 | Θ(n) |
| 별칭 | 동적 테이블 확장 가능한 배열 동적 배열 |
|---|---|
| 사용 사례 | 해시 테이블 힙 |
-
분할 상환 자료 구조 -
스플레이 트리
스플레이 트리는 스플레이 연산을 통해 자가 균형을 유지하며 최근 접근 노드의 빠른 접근을 가능하게 하는 이진 탐색 트리로, 분할 상환 분석 시 평균적으로 O(log n)의 시간 복잡도를 가진다. -
분할 상환 자료 구조 -
피보나치 힙
피보나치 힙은 최소 힙 속성을 가진 트리들의 집합으로, 각 노드의 차수를 특정 로그 값 이하로 유지하여 효율적인 삽입, 병합, 최소값 검색 연산을 지원하며, 다익스트라 알고리즘과 같은 그래프 알고리즘의 성능 향상에 활용된다. -
배열 -
원형 버퍼
원형 버퍼는 고정 크기의 자료구조로, 처음과 끝이 연결되어 데이터가 순환하며 저장되는 FIFO 방식의 버퍼이며, 큐 구현, 멀티미디어 스트리밍, 데이터 압축 등에 활용된다. -
배열 -
할바흐 배열
할바흐 배열은 특정 면에 자기장을 집중시키고 다른 면에서는 상쇄시키는 배열로, 자장 격리에 유용하며 다양한 산업 및 첨단 기술 분야에 응용된다.
2. 작동 원리 및 특징
동적 배열은 그 크기가 고정되지 않고, 필요에 따라 자동으로 늘어나거나 줄어드는 배열이다. 이러한 특징은 데이터의 개수를 미리 예측하기 어렵거나, 데이터가 계속 추가/삭제되는 상황에서 유용하다.
동적 배열은 내부적으로 고정 크기 배열을 사용한다. 이 고정 크기 배열에 데이터를 순차적으로 저장하며, 남는 공간은 예비 공간으로 남겨둔다. 만약 데이터를 추가하다가 예비 공간이 부족해지면, 더 큰 크기의 새로운 배열을 할당하고 기존 데이터를 복사하는 방식으로 작동한다. 이 과정을 '크기 조정'이라고 하며, 일반적으로 현재 크기의 두 배로 늘리는 방식을 사용한다.
동적 배열의 끝에 요소를 추가하는 작업은 예비 공간이 충분하다면 상수 시간에 가능하다. 하지만 크기 조정이 필요한 경우에는 모든 요소를 복사해야 하므로 시간이 더 오래 걸린다. 이러한 크기 조정 비용에도 불구하고, 여러 번의 추가 작업을 고려하면 평균적으로 상수 시간에 가까운 성능을 보인다. 이를 상각 상수 시간이라고 한다.
동적 배열은 배열과 마찬가지로 특정 위치의 요소를 빠르게 읽거나 변경할 수 있다. 또한, 요소들이 메모리에 연속적으로 저장되기 때문에 캐시 효율성이 높다는 장점도 있다. 하지만 중간에 요소를 삽입하거나 삭제하는 경우에는 뒤쪽의 요소들을 모두 이동시켜야 하므로 시간이 오래 걸린다.
다음은 동적 배열과 다른 자료 구조들의 성능을 비교한 표이다.
| 조회 (인덱스) | 변경 (삽입 또는 삭제) | 초과 공간, 평균 | |||
|---|---|---|---|---|---|
| 시작 | 끝 | 중간 | |||
| 연결 리스트 | Θ(n) | Θ(1) | 끝 요소가 알려진 경우 Θ(1), 끝 요소가 알려지지 않은 경우 Θ(n) | Θ(n) | |
| 배열 | Θ(1) | 0 | |||
| 동적 배열 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(n) | |
| 균형 트리 | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | |
| 임의 접근 리스트 | Θ(log n) | Θ(1) | Θ(n) | ||
| 해시된 배열 트리 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(√n) | |
2.1. 용량과 크기 조정
간단한 동적 배열은 고정 크기 배열을 할당하여 구성할 수 있으며, 일반적으로 필요한 요소 수보다 크게 할당한다. 동적 배열의 요소는 기본 배열의 시작 부분에 연속적으로 저장되며, 나머지 위치는 예약되거나 사용되지 않는다. 동적 배열의 끝에 요소를 추가하는 것은 예약된 공간을 사용하여 상수 시간에 가능하다. 모든 공간이 소모된 경우, 기본 고정 크기 배열의 크기를 늘려야 한다. 일반적으로 크기 조정은 새 배열을 할당하고 원래 배열에서 각 요소를 복사해야 하므로 비용이 많이 든다. 크기 조정이 필요하지 않으므로 동적 배열의 끝에서 요소를 상수 시간에 제거할 수 있다.
동적 배열 내용에서 사용되는 요소의 수는 논리적 크기 또는 크기이며, 기본 배열의 크기는 동적 배열의 용량 또는 물리적 크기라고 하며, 이는 데이터를 재배치하지 않고 가능한 최대 크기이다.
동적 배열은 크기를 두 배로 늘리는 등 큰 폭으로 크기를 조정하며, 미래 확장을 위해 예약된 공간을 사용한다. n개의 요소가 삽입되면, 용량은 기하 수열을 형성한다. 배열을 임의의 상수 비율 a로 확장하면 n개의 요소를 삽입하는 데 전체적으로 O(n) 시간이 걸리도록 보장하며, 이는 각 삽입이 상각 상수 시간이 걸린다는 의미이다. 많은 동적 배열은 크기가 용량의 특정 임계값, 예를 들어 30% 미만으로 떨어지면 기본 스토리지를 일부 할당 해제한다.
동적 배열의 성장 인자는 공간-시간 트레이드 오프 및 메모리 할당기 자체에 사용되는 알고리즘을 포함한 여러 요인에 따라 달라진다. 성장 인자 a에 대해 삽입 연산당 평균 시간은 약 a/(a−1)이며, 낭비되는 셀 수는 (a−1)n로 상한을 둔다. 황금비율과 1.5 값을 포함하여 이상적인 성장 인자 값에 대한 다양한 논의가 있어왔다. 그러나 많은 교과서에서는 단순성과 분석 목적으로 a = 2를 사용한다.
다음은 몇 가지 인기 있는 구현에서 사용되는 성장 인자이다.
2.2. 성장 인자 (Growth Factor)
동적 배열은 크기를 조절할 때, 일반적으로 현재 크기의 두 배로 늘리는 방식을 사용한다. 이는 잦은 크기 조정으로 인한 비용을 줄이고, 미래에 추가될 요소를 위한 공간을 확보하기 위함이다.
예를 들어, n개의 요소를 동적 배열의 끝에 추가하면, 배열의 용량은 기하 수열 형태로 증가한다. 배열의 크기를 상수 비율 a로 늘리면, n개의 요소를 추가하는 데 걸리는 총 시간은 O(n)이 된다. 즉, 각 요소 추가 작업은 상각 상수 시간이 걸린다.
동적 배열의 성장 인자는 공간-시간 트레이드 오프 등 여러 요인에 따라 결정된다. 성장 인자 a에 대해 삽입 연산당 평균 시간은 약 a / (a - 1)이며, 낭비되는 셀 수는 (a - 1)n을 상한으로 한다. 메모리 할당 알고리즘에 따라서는 성장 인자 값 a = 2와 같은 값은 상당한 양의 메모리가 여전히 사용 가능하더라도 동적 배열 확장이 메모리 부족으로 실행될 수 있다. 황금비율과 1.5 값을 포함하여 이상적인 성장 인자 값에 대한 다양한 논의가 있어왔다. 그러나 많은 교과서에서는 단순성과 분석 목적으로 a = 2를 사용한다.
몇 가지 프로그래밍 언어 및 구현체 별 성장 인자는 다음과 같다.
2.3. 성능 분석
동적 배열은 배열과 유사한 성능을 가지면서도, 요소를 추가하고 제거하는 새로운 연산을 제공한다.
* 특정 인덱스의 값을 가져오거나 설정 (상수 시간)
* 순서대로 요소 반복 (선형 시간, 좋은 캐시 성능)
* 배열 중간에 요소 삽입 또는 삭제 (선형 시간)
* 배열 끝에 요소 삽입 또는 삭제 (상수 상각 시간)
동적 배열은 참조 지역성 및 데이터 캐시 활용, 압축성(낮은 메모리 사용량), 그리고 임의 접근 등 배열의 여러 장점을 가진다. 일반적으로 크기와 용량 정보를 저장하기 위한 작고 고정된 추가 오버헤드만 발생한다. 이러한 특징은 동적 배열을 캐시 친화적인 자료 구조를 구축하기 위한 매력적인 도구로 만든다. 그러나 파이썬이나 자바와 같이 참조 의미론을 사용하는 언어에서는 동적 배열이 실제 데이터를 저장하는 대신, 메모리의 다른 영역에 있는 데이터에 대한 참조를 저장한다. 이 경우 배열의 항목에 순차적으로 접근하면 여러 개의 인접하지 않은 메모리 영역에 접근하게 되어, 자료 구조의 캐시 친화성이 가지는 많은 장점이 사라진다.
연결 리스트와 비교했을 때, 동적 배열은 더 빠른 인덱싱 (상수 시간 대 선형 시간)을 가지며, 참조 지역성이 개선되어 일반적으로 더 빠른 반복을 수행한다. 하지만 동적 배열은 임의의 위치에 삽입하거나 삭제하는 데 선형 시간이 필요하다. 모든 후속 요소를 이동해야 하기 때문이다. 반면 연결 리스트는 이를 상수 시간 내에 수행할 수 있다. 이러한 단점은 갭 버퍼 및 계층적 벡터 변형에서 완화된다. 또한, 고도로 단편화된 메모리 영역에서는 큰 동적 배열에 대한 인접 공간을 찾는 것이 비싸거나 불가능할 수 있지만, 연결 리스트는 전체 자료 구조를 인접하게 저장할 필요가 없다.
균형 트리는 동적 배열과 연결 리스트의 모든 연산을 합리적으로 효율적으로 제공하면서 리스트를 저장할 수 있다. 그러나 끝에 삽입하고 리스트를 반복하는 것은 비인접 저장 및 트리 순회/조작 오버헤드로 인해 이론적으로나 실제적으로 동적 배열보다 느리다.
| 조회 (인덱스) | 변경 (삽입 또는 삭제) | 초과 공간, 평균 | |||
|---|---|---|---|---|---|
| 시작 | 끝 | 중간 | |||
| 연결 리스트 | Θ(n) | Θ(1) | 끝 요소가 알려진 경우 Θ(1), 끝 요소가 알려지지 않은 경우 Θ(n) | Θ(n) | |
| 배열 | Θ(1) | 0 | |||
| 동적 배열 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(n) | |
| 균형 트리 | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | |
| 임의 접근 리스트 | Θ(log n) | Θ(1) | Θ(n) | ||
| 해시된 배열 트리 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(√n) | |
3. 변형
갭 버퍼는 동적 배열과 유사하지만 동일한 임의 위치 근처에서 삽입 및 삭제 작업을 효율적으로 수행할 수 있게 해준다. 일부 데크 구현은 배열 데크를 사용하는데, 이는 한쪽 끝뿐만 아니라 양쪽 끝에서도 분할 상환 상수 시간으로 삽입/제거를 할 수 있게 해준다.
Goodrich는 배열의 어느 곳에서나 삽입 및 삭제에 대해 O(n1/k) 성능을 제공하고, O(k)의 접근 및 설정 시간을 가지는 '계층적 벡터'(tiered vectors)라는 동적 배열 알고리즘을 제시했다. 여기서 k ≥ 2는 상수 매개변수이다.
1999년 논문에서 Brodnik et al.은 매 시점 n개 요소에 대해 n1/2 공간만 낭비하는 계층화된 동적 배열 데이터 구조를 설명하고, 모든 동적 배열이 분할 상환 상수 시간을 유지하려면 이만큼의 공간을 낭비해야 한다는 하한을 증명했다. 또한 버퍼를 확장 및 축소하는 것이 분할 상환뿐만 아니라 최악의 경우에도 상수 시간이 걸리는 변형을 제시했다.
단순하게 크기를 조절할 수 있는 배열은 배열에 추가되는 모든 항목에 대해 realloc을 호출하여 배열에 포함된 모든 데이터에 정확히 충분한 할당된 크기를 유지한다. 이는 C에서 크기를 조절할 수 있는 배열을 구현하는 가장 간단한 방법이지만, 메모리를 낭비하지 않는 대신 배열의 끝에 추가하는 데 항상 Θ(n) 시간이 걸린다.
선형으로 증가하는 배열은 배열의 크기를 조정할 때마다 Θ(1) 공간을 미리 할당("낭비")하므로 단순하게 크기를 조절할 수 있는 배열보다 훨씬 빠르다. 배열의 끝에 추가하는 데 여전히 Θ(n) 시간이 걸리지만, 상수가 훨씬 작다.
단순하게 크기를 조절할 수 있는 배열과 선형으로 증가하는 배열은 공간이 제한된 응용 프로그램에서 많은 소규모의 크기를 조절할 수 있는 배열이 필요할 때 유용할 수 있으며, 지수적으로 증가하는 동적 배열로 이어지는 교육적인 예제로도 흔히 사용된다.
3.1. 갭 버퍼 (Gap Buffer)
갭 버퍼는 동적 배열과 유사하지만 동일한 임의 위치 근처에서 클러스터링된 삽입 및 삭제 작업을 효율적으로 수행할 수 있다. 일부 데크 구현은 배열 데크를 사용하는데, 이는 한쪽 끝뿐만 아니라 양쪽 끝에서도 분할 상환 상수 시간으로 삽입/제거를 할 수 있다.
3.2. 계층적 벡터 (Tiered Vectors)
Goodrich는 배열의 어느 곳에서나 삽입 및 삭제에 대해 O(n1/k) 성능을 제공하고 O(k)를 얻고 설정하는 '계층적 벡터'(tiered vectors)라는 동적 배열 알고리즘을 제시했으며, 여기서 k ≥ 2는 상수 매개변수이다.
해시 배열 트리(HAT)는 1996년 Sitarski에 의해 발표된 동적 배열 알고리즘이다. 해시 배열 트리는 배열의 요소 수가 n일 때 n1/2 차수의 저장 공간을 낭비한다. 이 알고리즘은 해시 배열 트리의 끝에 일련의 객체를 추가할 때 O(1) 분할 상환 성능을 갖는다.
1999년 논문에서 Brodnik et al.은 매 시점 n개 요소에 대해 n1/2 공간만 낭비하는 계층화된 동적 배열 데이터 구조를 설명하고, 모든 동적 배열이 분할 상환 상수 시간을 유지하려면 이만큼의 공간을 낭비해야 한다는 하한을 증명했다. 또한 버퍼를 확장 및 축소하는 것이 분할 상환뿐만 아니라 최악의 경우에도 상수 시간이 걸리는 변형을 제시했다.
Bagwell (2002)은 동적 배열을 구현하는 데 적용할 수 있는 VList 알고리즘을 제시했다.
3.3. 해시 배열 트리 (Hashed Array Tree, HAT)
해시 배열 트리(HAT)는 1996년 시타르스키(Sitarski)가 발표한 동적 배열 알고리즘이다. 해시 배열 트리는 배열의 요소 수가 n일 때 n1/2 크기의 저장 공간을 낭비한다. 이 알고리즘은 해시 배열 트리의 끝에 일련의 객체를 추가할 때 O(1) 분할 상환 성능을 갖는다.
4. 언어 지원
C++의 `std::vector`와 러스트의 `std::vec::Vec`은 동적 배열의 구현이며, 자바 API와 .NET Framework에서 제공되는 `ArrayList` 클래스도 동적 배열의 구현이다.
.NET Framework 버전 2.0에서 제공되는 제네릭 `List<>` 클래스 또한 동적 배열로 구현된다. 스몰토크의 `OrderedCollection`은 동적 시작 및 종료 인덱스를 가진 동적 배열로, 첫 번째 요소 제거도 O(1)이다.
파이썬의 `list` 데이터 타입 구현은 동적 배열이며, 증가 패턴은 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...이다.
델파이와 D는 언어의 핵심에서 동적 배열을 구현한다.
Ada의 `Ada.Containers.Vectors` 제네릭 패키지는 주어진 서브타입에 대한 동적 배열 구현을 제공한다.
펄과 루비와 같은 많은 스크립트 언어는 동적 배열을 내장 원시 자료형으로 제공한다.
C를 위한 여러 크로스 플랫폼 프레임워크는 Core Foundation의 `CFArray`와 `CFMutableArray`, GLib의 `GArray`와 `GPtrArray`를 포함하여 동적 배열 구현을 제공한다.
Common Lisp는 내장된 `array` 타입을 조절 가능(adjustable)으로 구성하고 삽입 위치를 채우기 포인터(fill-pointer)로 구성하여 크기 조절 가능한 벡터에 대한 기본적인 지원을 제공한다.