[실압코] 배열 (vector)

서론

 오늘은 코딩테스트(PS)에서 가장 기본이 되면서도 많이 사용되는 자료구조인 배열에 대해 알아보겠습니다.

 배열은 크게 컴파일 타임에 크기가 고정되는 정적 배열과 프로그램 실행 중에 크기가 변할 수 있는 동적 배열로 나뉩니다. 오늘 포스팅에서는 정적 배열은 C++ 기본 문법을, 동적 배열은 STL의 벡터(vector)를 기준으로 설명하겠습니다. 또한 배열을 전역공간과 지역공간에 선언했을 때의 차이점도 함께 짚어보겠습니다.

정적 배열

 코딩 테스트 환경에서는 주로 벡터를 사용하지만, 버퍼나 고정된 크기의 배열을 다룰 때는 정적 배열이 유용할 때가 있습니다.

int arr0[5];                       // 크기가 5, 초기화 안 함(쓰레기값)
int arr1[5] = {};                  // 크기가 5, 모든 값을 0으로 초기화
int arr2[] = { 1, 2, 3, 4, 5 };    // 크기가 5, 1~5로 초기화

int arr3[5][5];                    // 5*5 행렬, 초기화 안 함(쓰레기값)
int arr4[5][5] = {};               // 5*5 행렬, 모든 값을 0으로 초기화

동적 배열

 크기가 변할 수 있는 동적 배열은 벡터를 사용합니다. 벡터를 다양하게 활용하기 위해서는 이터레이터(iterator) 개념을 알아야 합니다. 이터레이터는 쉽게 말하면 배열의 원소를 가리키는 포인터입니다. 증가할수록 배열의 뒤로 이동하고 감소할수록 배열의 앞으로 이동하며 배열의 특정 위치를 가리키거나 탐색할 때 사용합니다. 대표적으로 배열의 시작점을 가리키는 begin()과 끝을 가리키는 end()가 있습니다. 앞에 r이 붙은 rbegin과 rend는 역방향 이터레이터라서 증가하면 배열의 앞으로 가고 감소하면 배열의 뒤로 갑니다.

v0.begin();     // v0의 첫 원소의 위치
v0.end();       // v0의 마지막 원소의 다음 위치
v0.rbegin();    // v0의 마지막 원소의 위치
v0.rend();      // v0의 첫 원소의 이전 위치

 

 벡터를 선언하기 위해 <vector> 헤더를 include 하여 사용합니다. 벡터의 기본 선언 방법은 다음과 같습니다. 아래 나온 방법 정도만 숙지하고 있다면 2차원 이상의 고차원 배열을 선언하는데도 문제가 없습니다. 

#include <vector>

using namespace std;

vector<int> v0;                                  // 빈 벡터
vector<int> v1(5);                               // 크기가 5이고 모든 값을 0으로 초기화
vector<int> v2(5, 1);                            // 크기가 5이고 모든 값을 1로 초기화
vector<int> v3 = { 1, 2, 3, 4, 5 };              // 크기가 5이고 1..5로 초기화

vector<int> v4 = v3;                             // v3 전체를 복사
vector<int> v5(v4.begin(), v4.begin() + 3);      // 앞에서부터 3개의 원소를 복사

vector<vector<int>> v6;                          // 크기가 0인 2차원 vector
vector<vector<int>> v7(5, vector<int>(5));       // 크기가 5*5이고 모든 값을 0으로 초기화
vector<vector<int>> v8(5, vector<int>(5, 1));    // 크기가 5*5이고 모든 값을 1로 초기화

 

 이번엔 벡터의 다양한 멤버함수들 중 자주 쓰이는 함수들을 알아보겠습니다. 먼저 배열에 원소를 추가하거나 제거하는 함수를 알아보겠습니다. 벡터의 back을 기준으로 삽입 삭제하는 pop_back()과 push_back()은 시간복잡도가 O(1) insert()와 erase()는 O(n)이므로 주의해야 합니다.

    v0.pop_back();         // 배열의 마지막 원소를 제거
    v0.push_back(1);       // 배열 마지막에 원소를 삽입
    v0.insert(iter, 1);    // iterator 위치에 1을 삽입
    v0.erase(iter);        // iterator 위치의 원소를 제거

 

 벡터의 현재 상태를 확인하거나 값을 가져오는 함수들을 알아보겠습니다.

v0.front();    // 배열의 첫 원소를 반환
v0.back();     // 배열의 마지막 원소를 반환
v0.size();     // 배열의 크기를 반환
v0.empty();    // 배열의 크기가 0이라면 true 아니면 false를 반환

 

 벡터에는 size와 capacity라는 두 가지 크기 개념이 있습니다.

• size: 실제 들어있는 데이터의 개수
• capacity: 메모리에 할당된 여유 공간의 크기

 데이터가 추가되어 size가 capacity를 초과하면, 벡터는 내부적으로 메모리 재할당을 수행합니다. 이 과정은 비용이 크기 때문에, 크기를 대략 알 수 있다면 reserve를 사용하여 미리 필요한 capacity를 확보하는 것이 효율적입니다.

 

v0.reserve(10);     // 내부적으로 10크기 만큼의 capacity를 확보
v0.resize(5);       // 배열의 size를 5로 변경 (늘어나면 0 초기화, 줄어들면 삭제)
v0.assign(5, 1);    // 배열의 size를 5로 변경하고 모든 값을 1로 초기화
v0.clear();         // 배열의 size를 0으로 변경

 

 마지막으로 배열의 모든 원소를 효율적으로 다루는 함수들을 소개하겠습니다. fill과 move는 벡터의 멤버함수는 아니지만 함께 자주 사용하기 때문에 소개하겠습니다.

• swap은 내부 포인터만 교환하므로 시간복잡도가 O(1)으로 두 벡터의 모든 원소를 교환할 수 있습니다.
• fill은 벡터의 이터레이터를 사용하여 반복문 없이 원하는 값으로 초기화할 수 있습니다.
• move는 O(1)으로 벡터의 값을 이동시킬 수 있습니다. 이때 v0는 빈 껍데기가 됩니다.

    v0.swap(v1);                      // v0와 v1의 모든 원소를 교환
    
    #include <algorithm>
    fill(v0.begin(), v0.end(), 1);    // v0의 모든 원소를 1로 초기화
    
    #include <utility>
    v1 = move(v0);                    // v1를 v0의 원소로 교체, v0는 쓰레기값으로 초기화

전역공간 vs 지역공간

 서론에서 언급했듯이, 배열을 어디에 선언하느냐에 따라 큰 차이가 있습니다. PS에서는 아래와 같은 이유로 크기가 큰 배열은 전역 변수로 선언하는 것이 안전하고 편리합니다.

메모리 영역:

• 전역 변수: 데이터 영역에 할당되며, 프로그램이 종료될 때까지 유지됩니다. 메모리 제한이 넉넉합니다.
• 지역 변수: 스택 영역에 할당됩니다. 스택은 크기가 제한적이라 너무 큰 배열(예: int a[1000000])을 선언하면 스택 오버플로우가 발생할 수 있습니다.

초기화:

• 전역 변수: 별도의 초기화 코드가 없어도 자동으로 0으로 초기화됩니다.
• 지역 변수: 초기화하지 않으면 쓰레기값이 들어갑니다.

결론

 오늘은 배열에 대해 알아봤습니다. 자주 쓰는 자료구조이니 만큼 잘 알아야 한다고 생각해서 열심히 정리해 봤습니다. 감사합니다.