Data Structures/Linear Data Structures

1.1.2 Dynamic Array

개념

동적 배열은 원소 수에 따라 저장 공간을 조절하는 배열입니다. C++의 vector, Java의 ArrayList, Python의 list가 대표적입니다.

1차원 동적 배열

크기와 용량

현재 원소 수를 크기, 확보한 저장 공간을 용량이라고 합니다. 뒤에 원소를 추가할 때 용량이 충분하면 새 값만 기록합니다. 용량이 가득 차면 더 큰 공간을 확보하고 기존 값을 옮깁니다.

다음 동적 배열에는 10,2010,20이 저장되어 있습니다. 원소 수는 22이고 용량은 33이므로 한 칸이 비어 있습니다.

10 20
▲ [그림 1] 동적 배열의 원소 추가 — 연산 전

뒤에 3030을 추가하면 비어 있던 칸에 3030이 저장되어 크기가 33이 됩니다.

10 20 30
▲ [그림 2] 동적 배열의 원소 추가 — 연산 후

선언과 초기화

항목C++JavaPython
선언vector<int> v;ArrayList<Integer> lst;대입으로 생성
빈 배열 초기화선언 시 빈 배열 생성lst = new ArrayList<>();lst = []
원소가 NN개인 배열 초기화v.assign(n, 0);lst = new ArrayList<>(Collections.nCopies(n, 0));lst = [0] * n

접근과 크기 조절

연산C++JavaPython
뒤에 추가v.push_back(x)lst.add(x)lst.append(x)
인덱스로 읽기v[i]lst.get(i)lst[i]
뒤에서 제거v.pop_back()lst.remove(lst.size()-1)lst.pop()
크기 확인v.size()lst.size()len(lst)

Java의 ArrayList<Integer>에서 remove(i)는 인덱스 ii의 원소를 지웁니다. 값으로 지우려면 remove(Integer.valueOf(x))를 사용합니다. C++은 마지막 값을 back()으로 읽은 뒤 pop_back()으로 제거합니다.

시간·공간복잡도

원소 수 NN, 확보한 용량 CC를 기준으로 합니다.

구분대상복잡도
시간원소 하나 읽기·수정, 크기 확인O(1)O(1)
시간끝에 원소 추가최악 O(N)O(N), 분할 상환 O(1)O(1)
시간끝에서 원소 제거분할 상환 O(1)O(1)
시간가운데 원소 삽입·삭제O(N)O(N)
공간확보한 배열 전체O(C)O(C)

2차원 동적 배열

2차원 동적 배열은 각 행을 동적 배열로 저장하는 구조입니다. 바깥 배열의 크기가 행의 수이고, 각 행의 크기가 해당 행의 열의 수입니다. 행을 추가하거나 제거할 수 있으며, 각 행의 길이도 독립적으로 조절할 수 있습니다.

다음 배열의 첫 번째 행에는 1,21,2가, 두 번째 행에는 33이 저장되어 있습니다.

행 0 행 1 1 2 3
▲ [그림 3] 2차원 동적 배열의 행 확장 — 연산 전

첫 번째 행의 뒤에 99를 추가하면 그 행의 길이가 33으로 늘어납니다.

행 0 행 1 1 2 9 3
▲ [그림 4] 2차원 동적 배열의 행 확장 — 연산 후

선언과 초기화

모든 값이 00인 nn행 mm열 배열을 만듭니다.

항목C++JavaPython
선언vector<vector<int>> v;ArrayList<ArrayList<Integer>> lst;대입으로 생성
초기화v.assign(n, vector<int>(m, 0));lst = new ArrayList<>(); 실행 후 각 행을 추가lst = [[0] * m for _ in range(n)]

Java는 lst.add(new ArrayList<>(Collections.nCopies(m, 0)));를 nn번 실행하여 행을 추가합니다. 각 행은 별도의 배열로 생성합니다.

접근과 크기 조절

i는 행 인덱스, j는 열 인덱스입니다.

동작C++JavaPython
원소 읽기v[i][j]lst.get(i).get(j)lst[i][j]
원소 수정v[i][j] = x;lst.get(i).set(j, x);lst[i][j] = x
행의 수v.size()lst.size()len(lst)
특정 행의 길이v[i].size()lst.get(i).size()len(lst[i])
특정 행의 끝에 추가v[i].push_back(x);lst.get(i).add(x);lst[i].append(x)
특정 행의 끝에서 제거v[i].pop_back();lst.get(i).remove(lst.get(i).size() - 1);lst[i].pop()
빈 행 추가v.push_back(vector<int>());lst.add(new ArrayList<>());lst.append([])
마지막 행 제거v.pop_back();lst.remove(lst.size() - 1);lst.pop()

제거 연산은 대상 원소나 행이 있을 때 수행합니다.

시간·공간복잡도

바깥 배열의 용량 RR, 각 행의 용량을 합한 값 CC를 기준으로 합니다.

구분대상복잡도
시간원소 하나 읽기·수정O(1)O(1)
시간특정 행의 끝에 원소 추가분할 상환 O(1)O(1)
공간바깥 배열과 모든 행의 저장 공간O(R+C)O(R+C)

예제

문제

처음에 비어 있는 동적 배열에 다음 명령을 순서대로 수행하여라.

명령동작
append x맨 뒤에 xx를 추가한다.
get i인덱스 ii의 값을 출력한다.
pop마지막 값을 출력하고 제거한다. 빈 배열이면 EMPTY를 출력한다.
size원소 수를 출력한다.

입력

첫째 줄에 명령 수 QQ가 주어진다. 1≤Q≤10 0001\le Q\le10\,000이다.

다음 QQ개 줄에 위 표의 형식으로 명령이 하나씩 주어진다. 명령과 인자는 공백을 사이에 두고 주어진다. 추가할 값 xx의 범위는 1≤x<10 0001\le x<10\,000이다. get의 인덱스 ii는 00 이상 현재 원소 수 미만이다.

출력

출력이 필요한 명령의 결과를 한 줄에 하나씩 출력한다.

예제 입력

7
append 10
append 20
get 0
size
pop
pop
pop

예제 출력

10
2
20
10
EMPTY

예제 코드

C++20

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> v;

int main() {
    int q, i, x, j;
    string op;

    cin >> q;

    for (i = 0; i < q; ++i) {
        cin >> op;

        if (op == "append") {
            cin >> x;

            v.push_back(x);
        }
        else if (op == "pop") {
            if (v.empty()) cout << "EMPTY\n";
            else {
                cout << v.back() << '\n';
                v.pop_back();
            }
        }
        else if (op == "get") {
            cin >> j;
            cout << v.at(j) << '\n';
        }
        else cout << v.size() << '\n';
    }
}