동적 배열 - 알고리즘카

배열은 인덱스로 접근하는 같은 타입의 변수들의 집합입니다.

동적 배열 또는 확장 가능한 배열은 배열에 들어 있는 원소의 개수에 따라 크기를 바꿀 수 있는 배열입니다.

동적 배열은 보통 배열의 크기를 미리 예측하기 어렵거나 불가능할 때 사용합니다. 이러한 맥락에서 동적 배열에는 임의의 원소에 접근하고 변경하는 연산 외에도 세 가지 연산이 더 있습니다.

배열의 끝에 원소 $x$를 추가합니다.
배열의 마지막 원소를 삭제합니다.
배열의 크기를 알아냅니다.

이때 모든 연산은 $O(1)$에 수행되어야 합니다. 최악의 경우에 반드시 그럴 필요는 없지만, 분할 상환으로는 그래야 합니다.

#구현

동적 배열은 이 단원의 모든 자료 구조와 마찬가지로 거의 모든 프로그래밍 언어에 존재하지만, 온전히 이해하려면 처음부터 직접 작성하는 법을 익혀 두기를 강력히 권장합니다. 동적 배열은 이후 다른 모든 자료 구조에서 사용되기 때문입니다.

일반 배열이 단순히 메모리상의 연속된 영역이라면, 동적 배열은 보통 다음을 포함하는 구조체로 구현합니다:

배열 $t$에 대한 포인터,
이 배열의 크기,
현재 원소의 개수(배열 $t$의 크기보다 작은 값).

이때 내부 배열 $t$가 완전히 가득 차 있는 상태에서 원소를 하나 더 추가해야 하면 배열을 확장합니다(할당을 해제하고 더 큰 크기로 다시 할당합니다). 또한 선택적으로, 채워진 원소의 비율이 작아지면 배열을 축소할 수도 있습니다. 이렇게 하면 사용하지 않는 메모리를 반환할 수 있습니다.

template <typename T>
struct dynamic_array {
    T *t;
    int size = 0, capacity;
    
    dynamic_array(int capacity) : capacity(capacity) {
        t = new T[capacity];
    }

    void resize(int new_capacity) {
        T *new_t = new T[new_capacity];
        memcpy(new_t, t, sizeof(T) * size);
        delete[] t;
        t = new_t;
    }

    T get(int k) {
        return t[k];
    }

    T set(int k, T x) {
        t[k] = x;
    }

    void add(T x) {
        if (size == capacity)
            resize(2 * capacity);
        t[size++] = x;
    }

    void del() {
        // если хотим сэкономить память:
        if (4 * size < capacity)
            resize(capacity / 2);
        size--;
    }
};

#실행 시간

최악의 경우 추가 및 삭제 연산은 선형 시간에 동작합니다. 크기가 $O(n)$인 배열 전체를 다시 만들어야 하기 때문입니다. 그러나 분할 상환 관점에서는 모든 연산이 $O(1)$에 동작합니다. 이를 보이기 위해 선불 방법을 적용해 봅시다.

#add

연산 비용의 단위를 동전 한 개라고 합시다. 그러면 복사가 필요하지 않은 각 add 연산마다 동전 세 개를 지불하게 됩니다. 그중 하나는 이 연산 자체의 비용으로 쓰이고, 나머지 두 개는 예비로 남겨 둡니다. 즉, $k$번째 원소를 추가했다면 번호가 $k$와 $(k−\frac{n}{2})$인 원소 옆에 동전을 하나씩 놓아 둡니다.

배열이 가득 찰 때쯤이면 각 원소 옆에 동전이 하나씩 놓여 있게 되며, 바로 이 동전으로 해당 원소를 새 배열로 복사하는 비용을 지불할 수 있습니다. 따라서 각 add 연산의 분할 상환 비용은 3이며, 평균 실행 시간은 $O(1)$입니다.

#del

일반적인 del 연산을 할 때마다 동전 두 개를 지불하겠습니다. 그중 하나는 마지막($k$번째) 원소를 직접 삭제하는 데 사용하고, 다른 하나는 $(k \bmod \frac{n}{4})$ 위치에 있는 원소 옆에 놓아 둡니다. 그러면 최악의 경우, 즉 방금 확장한 뒤 끝에서부터 $\frac{n}{4}$개의 원소를 삭제한 경우에도 처음 $\frac{n}{4}$개의 원소마다 동전이 하나씩 놓여 있게 되며, 바로 이 동전들을 그 원소들을 옮기는 데 사용합니다.

#프로그래밍 언어에서

#std::vector

C++에서 동적 배열은 표준 라이브러리의 vector 구조체로 구현되어 있습니다.

// создать пустой вектор
vector<int> a;

// вставляет x в конец a
a.push_back(x);

// возвращает размер вектора а
a.size();

// сделать размер вектора = x
// либо удаляются последние элементы, либо добавляются нули
a.resize(x);

// сделать размер вектора = x, добавляются y
a.resize(x, y);

// при инициализации можно изначально задать размер и элементы массива
vector<int> a(8);         // {0, 0, 0, 0, 0, 0, 0, 0}
vector<int> b(5, 42);     // {42, 42, 42, 42, 42}
vector<int> c = {1, 2, 3} // {1, 2, 3}

메모리가 가득 찬 상태에서 배열에 새 원소를 쓰려고 하면 크기가 늘어나는데, GCC로 컴파일하면 2배, MSVC로 컴파일하면 1.5배로 늘어납니다. 원소를 삭제해도 배열의 크기는 줄어들지 않습니다.

vector의 capacity는 같은 이름의 함수를 사용하여 얻을 수 있습니다:

vector<int> a;
for (int i = 0; i < 10; i++) {
    a.push_back(i);
    cout << "size: " << a.size() << ", capacity " << a.capacity() << endl;
}

다음과 같이 출력됩니다:

size: 1, capacity 1
size: 2, capacity 2
size: 3, capacity 4
size: 4, capacity 4
size: 5, capacity 8
size: 6, capacity 8
size: 7, capacity 8
size: 8, capacity 8
size: 9, capacity 16
size: 10, capacity 16

vector를 기본값으로 초기화하면 초기 크기(capacity)는 0이지만, 내부적으로 이를 사용하는 많은 구조체는 원소가 하나만 저장되지는 않으리라는 가정하에 시간을 절약하기 위해 16이나 32개 원소와 같은 일정한 초기 크기를 미리 예약해 두는 경우가 많습니다.

#Python

파이썬에서는 일반 리스트가 확장 가능한 배열의 역할을 합니다.

a = [1, 2, 3]
a.append(4)