Vector(벡터)

개념

벡터(Vector)는 동적(dynamic) 배열 자료구조입니다.

먼저 배열(array)에 대한 이해가 필요합니다.

벡터는 내부 배열에 요소들을 저장하며, 이 배열의 크기는 내부 변수 capacity 값에 해당합니다. 실제 쓰이는 공간, 즉 요소의 개수는 내부 변수 size 값에 해당합니다. 요소의 추가 및 삭제 시 필요에 따라 동적으로 적절한 크기의 배열을 새로 할당하고 기존 값을 복사하여 저장합니다.

요소에 접근할 때에는 배열과 마찬가지로 인덱스(Index)를 사용하여 빠르게 접근할 수 있습니다.

벡터의 용량, 크기, 그리고 요소라 함은 일반적으로 벡터 내부 배열의 용량과 내부 size 값, 내부 배열의 요소를 의미합니다.

동적 크기 조절

벡터 사용자에게 추가(push_back) 및 삭제(pop_back, erase) 기능을 제공합니다. 추가 및 삭제 시 size 값을 변경하며, 이때 size가 capacity를 초과하거나 너무 작아지면 배열의 크기를 동적으로 resize 합니다.

추가(push_back): 요소를 배열의 마지막 요소 다음(index: size)에 추가합니다. 이때 만약 size와 capacity 값이 같으면, 더 큰 capacity 값(보통 2배)으로 resize하고 나서 요소를 추가하고 size를 1 증가시킵니다.
삭제(pop_back/erase): size를 1 감소시켜 마지막 요소가 삭제된 것으로 간주합니다. 필요에 따라 capacity에 비해 size가 너무 작아지면(보통 1/4) 더 작은 capacity 값(보통 1/2)으로 resize할 수 있습니다.
resize: 새 capacity 값을 매개변수로 받아 해당 크기의 새 배열을 동적으로 할당받습니다. 기존 배열의 요소들(size 개)을 새 배열로 복사한 후, 내부 배열 변수를 새 배열로 변경하고, 기존 배열은 해제(delete/free)합니다. 내부 capacity 변수 값을 새 capacity 값으로 변경합니다.
- 단, resize만 수행했을 떈 size 값은 변경되지 않습니다.
- 크기를 줄일 때 size가 새 capacity보다 클 수 있으며(즉, 일부 요소가 잘림), 상황에 따라 잘리는 요소들에 상관 없이 resize할 수도 있고, 잘리는 요소들이 없도록 capacity를 조절할 수도 있습니다.

주요 연산

일반적으로 벡터 자료구조가 제공하는 주요 연산들은 다음과 같습니다:

push_back(value): 벡터의 마지막에 value를 추가합니다.
pop_back(): 벡터의 마지막 요소를 제거합니다.
resize(new_capacity): 벡터의 capacity를 new_capacity로 변경합니다. 일반적으로 내부적으로만 접근 가능한 private 메서드입니다.

추가로 특정 위치에 접근하거나 조작, 상태 확인 등의 연산들을 구현하여 사용할 수 있습니다

size(): 내부 배열에 저장된 요소의 개수를 반환합니다.

capacity(): 내부 배열의 할당된 길이를 반환합니다.

is_empty(): 벡터가 비어있는지 여부를 반환합니다.

at(index): index 위치의 요소를 반환합니다.

front(): 벡터의 첫 번째 요소를 반환합니다.

back(): 벡터의 마지막 요소를 반환합니다.

insert(index, value): index 위치에 value를 삽입합니다. resize가 필요할 수 있습니다.

erase(index): index 위치의 요소를 제거합니다. resize가 이뤄질 수 있습니다.

clear(): 벡터의 모든 요소를 제거하고 size를 0으로 설정합니다.

reserve(new_capacity): 내부 배열의 크기를 new_capacity 이상으로 할당합니다. 미리 일정 수준으로 capacity를 확보하고자 할 때 사용할 수 있으며, 이미 충분한 capacity가 있으면 아무 동작도 하지 않습니다.

shrink_to_fit(): 현재 size에 맞게 capacity를 줄입니다.

시간 복잡도

벡터의 기본 구조와 작동 방식은 배열과 유사하지만, 동적 크기 조절 기능이 추가되어 요소의 추가 및 삭제 시의 효율성을 추가로 고려해야 합니다.

따라서 벡터의 주요 연산들에 대한 시간 복잡도는 다음과 같습니다:

연산	설명	시간 복잡도
생성	빈 벡터 생성	O(1)
생성	크기 n의 벡터 생성	O(n)
접근	인덱스 i의 요소에 접근	O(1)
변경	인덱스 i의 요소 값 변경	O(1)
추가	벡터의 마지막에 요소 추가	평균 O(1), 최악 O(n)
삭제	벡터의 마지막 요소 삭제	평균 O(1), 최악 O(n)
검색	특정 값의 요소 검색 (선형 탐색)	O(n)

추가 및 삭제 연산의 시간 복잡도 설명

추가(push_back) 및 삭제(pop_back) 연산은 resize 수행 여부에 따라 시간 복잡도가 달라집니다.

추가 연산의 경우를 먼저 살펴보겠습니다.

resize가 필요 없는 경우, size index에 값을 저장하고, size를 1 증가시키는 작업이므로 O(1).
resize가 필요한 경우, 새로운 배열 할당 및 기존 요소 복사 작업이 필요하므로 O(n). 정확히는 기존 요소의 복사에 O(size), 새 요소 추가에 O(1) 시간이 걸립니다.

resize는 size 값이 capacity 값에 도달할 때만 수행됩니다.

아래와 같이 크기 1의 벡터에 요소를 한 개씩 추가하며 2배씩 resize하는 과정에서 한 번의 추가 연산당 작업(복사 + 새 요소 추가) 횟수를 추적하여 추가 연산당 평균 시간 복잡도를 계산해보겠습니다.

추가 횟수	추가 횟수	복사 횟수	capacity 변화	resize 이후 누적 작업 횟수
1	1	0	-	-
2	1	1	1 -> 2	2
3	1	2	2 -> 4	3
4	1	0	-	4
5	1	4	4 -> 8	5
6	1	0	-	6
7	1	0	-	7
8	1	0	-	8
9	1	8	8 -> 9	9
…	…	0	…	10
16	1	0	-	16
17	1	16	16 -> 32	17
…	…	…	…	…

한 번 resize가 일어난 때부터 다음 resize 직전(미리 확보한 capacity를 모두 사용할 떄)까지 구간별로 해당 구간의 누적 작업 횟수는 다음과 같습니다.

추가 횟수 구간	추가 횟수	구간 작업 횟수	추가 연산당 작업 횟수 평균
2	1	2	2
3-4	2	4	2
5-8	4	8	2
9-16	8	16	2
17-32	16	32	2
…	…	…	…

각 구간에서 추가 연산 한 번당 평균 작업 횟수는 모두 2로 일정합니다.

resize가 발생할 때마다 필요한 복사 연산의 횟수가 2배로 늘어나지만, 다음 resize까지 필요한 추가 연산 횟수도 2배로 늘어납니다. 따라서, 추가 연산 한 번(O(1))당 분담하는 복사 연산의 횟수(O(1))는 추가 연산이 몇 번 이뤄지든지에 관계 없이 일정합니다.

따라서 추가 연산 한 번당 평균 시간 복잡도(작업 횟수)는 (평균 복사 연산(O(1)) + 새 요소 추가 연산(O(1))) = O(1)이 됩니다.

삭제 연산에서도 비슷하지만, 반대로 요소가 삭제되고 size가 줄어들며 resize가 발생합니다. 같은 방식으로 O(1)의 삭제 연산과 resize 시 발생하는 O(size)의 복사 연산을 고려하면 평균 시간 복잡도는 O(1)이 됩니다.

추가 설명

근본적으로, 새 요소를 하나 추가할 때 그만큼 공간을 할당받아 기존 배열에 더해 줄 필요가 있는데, 배열은 크기 변경이 불가능하므로 할당받은 공간을 기존 배열에 붙이거나 할 수 없습니다. (이런 작업은 Linked List에서 가능합니다.)

따라서 새 요소를 추가할 때마다 공간을 할당받는 게 아니라, 미리 적당한 크기(capacity)의 배열을 할당받아 놓고, 미리 할당받은 공간을 이용합니다. O(size)의 시간이 걸리는 복사 연산을 요소를 추가할 때마다 수행하는 것이 아니라, size에 반비례하는 빈도(즉, size가 capacity에 도달할 때마다)로 수행하여, 실제로 size가 커지는 만큼 평균적인 추가 연산 시간 복잡도를 O(1)로 유지하는 것입니다.

resize할 때 발생하는 복사 연산을 몰아서 한 번에 처리해 놓고, 나머지 추가 연산들은 미리 확보해 놓은 capacity를 이용해 빠르게 처리하는 것으로 볼 수 있습니다.

예시

다음은 cpp의 std::vector를 사용한 예시입니다.

#include <vector>

std::vector<int> vec;

vec.push_back(10);                  // 값 10 추가
vec.push_back(20);                  // 값 20 추가
vec.push_back(30);                  // 값 30 추가

int first = vec[0];                 // 첫 번째 요소: 10

vec[1] = 25;                        // 두 번째 요소 값 변경 (20 -> 25)
int second = vec[1];                // (변경된)두 번째 요소: 25

int last = vec[vec.size() - 1];     // vec.size() == 3, 마지막 요소: 30

vec.pop_back();                     // 마지막 요소 삭제 (30 삭제)

배열(arrary)와 비슷하게 선언 및 접근할 수 있습니다. 그러나 배열과 달리 선언 시 크기를 지정하지 않아도 요소를 추가할 때 자동으로 크기가 조절됩니다.

push_back, pop_back 등의 메서드로 요소를 추가 및 삭제할 수 있습니다. 벡터의 사용자는 이 과정에서 내부 배열의 용량을 신경 쓸 필요가 없습니다. 추가 및 삭제 과정에서 내부에서 자동으로 동적 크기 조절이 이뤄집니다.

참고

GitHub - 벡터 구현 예시(cpp) - cpp의 std::vector를 사용하지 않고 벡터 자료구조를 직접 구현한 예시

벡터는 배열의 장점(빠른 인덱스 접근)을 유지하면서, 동적 크기 조절을 통해 유연한 요소 관리가 가능해 다양한 상황에서 널리 사용됩니다. 대부분의 현대 프로그래밍 언어에서 벡터 또는 유사한 동적 배열 자료구조를 제공합니다.

단, 벡터의 동적 크기 조절이나 여러 요소 관리 기능들이 필요 없는 경우, 단순 배열을 사용하는 것이 성능 면에서 더 유리할 수 있습니다.