[C++, STL] 알고리즘 문제풀이를 위한 벡터(vector)

서론

우리는 다수의 자료를 저장하기 위해 배열을 사용한다. 그러나 배열은 임의의 위치에 원소를 삽입하거나 할당된 메모리가 꽉 찼을때 등 여러 상황에서 까다로운 문제가 발생한다. 이를 해결하기 위해 동적배열을 사용한다. 동적배열은 사용하면서 원소가 추가되면 메모리를 조금씩 추가 할당하며 대표적으로 리스트, 벡터가 있다.

리스트는 배열이 가지는 위 단점을 해결할 수 있다. 그러나 배열과 벡터는 원소에 직접 접근하여 탐색시간이 O(1)이지만 리스트는 처음부터 순회하여 탐색하기 때문에 탐색시간이 O(N)이다. 알고리즘 문제풀이 핵심은 시간복잡도를 줄이는것이다. 따라서 리스트는 다수의 경우에서 알고리즘 문제풀이에 적합하지 않다.

벡터는 임의의 위치에 자료를 추가/삭제하는 경우의 시간은 O(N)이지만 마지막 위치에 추가/삭제, 탐색하는 경우의 시간은 O(1)로 리스트 대비 빠르다.

결론적으로 동적배열이 필요하고 자료의 삽입/삭제보다 탐색이 빈번하다면 벡터를 사용해야 한다. 그리고 알고리즘 문제풀이는 대부분이 이 경우다.

벡터 사용

헤더파일

벡터를 사용하기 위해서는 헤더파일이 필요하다.

#include <vector>

벡터 선언

std::vector<템플릿>이름

std::vector<int>v; // int형 자료를 저장하는 벡터 v 생성

이후에는 글의 가독성을 위해 std를 생략한다. std는 네임스페이스(using namespace std)로 대체될 수 있다.

템플릿은 int, string, vector, struct 등 다양하게 들어갈 수 있다. 즉 벡터의 원소는 다양한 자료형이 들어갈 수 있다.

vector<템플릿>이름(int)

vector<int>v(3); // 0이 3개 저장된 벡터 v 생성.

vector<템플릿>이름(int, int)

vector<int>v(3, 8); // 8이 3개 저장된 벡터 v를 생성.

멤버함수

아래 벡터의 멤버함수는 알고리즘 풀이에서 자주 사용되는 것들이다. 모든 멤버함수는 아래 링크에서 확인할 수 있다.

https://docs.microsoft.com/ko-kr/cpp/standard-library/vector-class?view=vs-2019

push_back(원소), pop_back()

벡터의 끝에 원소를 추가하거나 삭제한다.

vector<int>v; // 빈 벡터 v를 생성한다. v = {}
v.push_back(4); // v에 원소 4를 추가한다. v = {4}
v.push_back(3); // v에 원소 3을 추가한다. v = {4, 3}
v.pop_back(); // v의 마지막 원소인 3을 지운다. v = {4}

operator[index]

배열과 같은 방법으로 벡터의 원소를 참조한다. v[0]은 v벡터의 첫번째 원소다.

vector<int>v(3); // 0이 3개 들어있는 v 생성

// v의 첫번째 원소부터 3번째 원소까지 출력
for(int i=0;i<3;i++) cout<< v[i] <<" "; // 출력 : 0 0 0

at(index)

벡터의 원소를 참조하는 또다른 방법이다.

operator[index]와는 다르게 참조할 인덱스가 벡터의 범위 밖을 벗어나는지 확인한 후 참조한다.

operator[index]보다 속도가 미미하게 느리기 때문에 조금의 시간소요라도 줄이고 싶다면 at(index) 대신 operator[index]를 사용한다.

vector<int>v(1); // v = {0}
cout<< v.at(0); // 출력 : 0
cout<< v.at(1); // 출력 : "terminate called after throwing an instance of 'std::out_of_range'"

https://stackoverflow.com/questions/2578638/c-vector-at-operator-speed

front(), back()

front와 back은 각각 벡터의 첫 원소와 마지막 원소를 참조한다.

vector<int>v; // v = {}
v.push_back(1); // v = {1}
v.push_back(2); // v = {1, 2}
cout<<v.front(); // 출력 : 1
cout<<v.back(); // 출력 : 2

begin(), end()

‘begin()’은 벡터의 첫 iterator(=첫 원소의 주소)를 리턴하고 ‘end()’는 벡터의 끝 iterator(=마지막 원소 다음 주소)를 리턴한다. iterator를 리턴하기 때문에 주로 정렬 알고리즘과 같이 iterator를 파라미터로 갖는 다른 STL과 활용한다.

sort(), max_element()와 같이 iterator를 파라미터로 가지는 STL들은 거의가 [first, last)이다.

[first, last) : [first는 첫 원소를 포함, last)는 마지막 원소를 포함하지 않음.

vector<int>v; // v = {}
v.push_back(2); // v = {2}
v.push_back(1); // v = {2, 1}
sort(v.begin(), v.end()); // v = {1, 2}

insert(a, b)

insert(a, b)는 벡터의 a위치에 b를 삽입한다. 이때 a는 iterator 값으로, v.begin()과 같이 활용할 수 있다. v.begin()은 첫 원소이며 v.begin() + 1은 두번째 원소, v.begin() + 2는 세번째 원소다.

vector<int>v; // v = {}
v.push_back(2); // v = {2}
v.push_back(1); // v = {2, 1}
v.insert(v.begin() + 1, 3); // v = {2, 3, 1}

erase(index), erase(start_index, end_index)

erase(index)는 벡터의 index 위치의 원소를 삭제한다. 이때 index는 iterator값으로, insert와 마찬가지로 활용할 수 있다.

erase(start_index, end_index)는 start_index 위치부터 end_index 직전 위치까지의 원소를 지운다.

vector<int>v(5, 8); // v = {8, 8, 8, 8, 8}
v.erase(v.begin()); // v의 첫번째 원소 삭제, v = {8, 8, 8, 8}
v.erase(v.begin(), v.begin() + 2); // v의 첫번째~두번째 원소 삭제, v = {8, 8}

size()

벡터의 원소 개수를 반환한다.

벡터 사이즈는 코드 실행 중에 가변적으로 변할때가 많기 때문에 유용하게 쓰인다.

vector<int>v; // v = {}
v.push_back(2); // v = {2}
cout << v.size(); // 출력 : 1
v.push_back(1); // v = {2, 1}
cout << v.size(); // 출력 : 2

empty()

벡터가 비어있으면 1, 아니면 0을 반환한다.

vector<int>v; // v = {}
cout << v.empty(); // 출력 : 1
v.push_back(2); // v = {2}
cout << v.empty(); // 출력 : 0

반복문과 함께 유용하게 쓰일 수 있다. 벡터의 원소가 하나씩 제거되는 반복문에서 조건문을 !empty()로 둔다면 벡터의 원소가 모두 제거될 때까지 반복하고 빠져나온다.

while(!v.empty()){
    v.pop_back();
}

clear()

벡터의 원소를 모두 제거한다.

vector<int>v; // v = {}
v.push_back(2); // v = {2}
v.clear(); // v = {}

참고