Vector

vector는 크기가 변할 수 있는 배열이다.

일반 배열과 마찬가지로 인덱스를 이용해 원소에 접근할 수 있으며, 실행 중에도 원소를 추가하거나 삭제할 수 있다.

헤더 파일

vector를 사용하려면 다음 헤더 파일을 포함해야 한다.

#include<vector>

보통 PS에서는 여러 표준 라이브러리를 한 번에 포함하기 위해 다음 헤더 파일을 사용한다.

#include<bits/stdc++.h>

선언

빈 vector는 다음과 같이 선언한다. $O(1)$

vector<int> v;

위 코드는 int 자료형의 원소를 저장하는 vector를 생성한다.

처음부터 크기를 정해 생성할 수도 있다. $O(n)$

vector<int> v(n);

이 경우 크기가 $n$인 vector가 생성된다.

초기값을 함께 지정할 수도 있다. $O(n)$

vector<int> v(n, -1);

위 코드는 크기가 $n$이고 모든 원소의 값이 $-1$인 vector를 생성한다.

원소 추가와 삭제

맨 뒤에 원소를 추가할 때는 push_back()을 사용한다. 보통 $O(1)$

v.push_back(10);
v.push_back(20);
v.push_back(30);

위 코드를 실행하면 vector에는 $10$, $20$, $30$이 차례대로 저장된다.

맨 뒤 원소를 삭제할 때는 pop_back()을 사용한다. $O(1)$

v.pop_back();

pop_back()은 마지막 원소를 삭제하지만, 삭제한 값을 반환하지는 않는다.

원소 접근

vector는 배열과 같은 방식으로 인덱스를 이용해 원소에 접근할 수 있다. $O(1)$

cout << v[0];
cout << v[1];

인덱스는 $0$부터 시작한다.
따라서 크기가 $n$인 vector에서 첫 번째 원소는 v[0], 마지막 원소는 v[n-1]이다.

맨 앞 원소와 맨 뒤 원소는 각각 front(), back()으로 확인할 수 있다. $O(1)$

cout << v.front();
cout << v.back();

단, 비어 있는 vector에서 front()나 back()을 호출하면 안 된다.

크기 확인

현재 저장된 원소의 개수는 size()로 확인한다. $O(1)$

cout << v.size();

비어 있는지는 empty()로 확인한다. $O(1)$

if(v.empty()) {
    cout << "empty";
}

empty()는 원소가 하나도 없으면 true, 그렇지 않으면 false를 반환한다.

2차원 vector

vector를 중첩하면 2차원 배열처럼 사용할 수 있다. $O(nm)$

vector<vector<int>> a(n, vector<int>(m));

위 코드는 $n$개의 행과 $m$개의 열을 갖는 2차원 vector를 생성한다.

초기값도 지정할 수 있다. $O(nm)$

vector<vector<int>> a(n, vector<int>(m, -1));

위 코드는 모든 원소의 값이 $-1$인 $n \times m$ 크기의 2차원 vector를 생성한다.

접근 방법은 배열과 같다.

a[i][j] = 10;
cout << a[i][j];

여기서 $i$는 행 인덱스, $j$는 열 인덱스를 의미한다.

연습 문제

C++ Vector

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    vector<int> v;
    int q; cin >> q;
    while(q--) {
        string s; int i, x; cin >> s;
        if(s=="push_back") {
            cin >> x;
            v.push_back(x);
        } else if(s=="pop_back") {
            v.pop_back();
        } else if(s=="front") {
            cout << v.front() << '\n';
        } else if(s=="back") {
            cout << v.back() << '\n';
        } else {
            cin >> i;
            cout << v[i] << '\n';
        }
    }
}