벡터 자료구조는 배열(Array)과 유사한 자료구조로, 연속된 메모리 공간에 원소들을 저장하는 자료구조입니다. 일반적으로 동적 배열(Dynamic Array)로 구현되며, 크기를 동적으로 조정할 수 있습니다. 다양한 프로그래밍 언어에서 지원되며, C++의 std::vector, Python의 list, Java의 ArrayList 등이 벡터 자료구조를 지원합니다.

벡터 자료구조의 주요 특징은 다음과 같습니다:

1. 연속된 메모리 공간 사용: 벡터는 연속된 메모리 공간에 원소들을 저장합니다. 이는 각 원소에 대한 접근이 빠르고 효율적이며, 메모리 효율성이 뛰어납니다.
2. 빠른 접근 및 삽입/삭제: 벡터는 배열과 유사하게 인덱스를 사용하여 원소에 빠르게 접근할 수 있습니다. 또한 벡터의 끝에 새로운 원소를 추가하거나 제거하는 연산도 상수 시간에 수행됩니다. 하지만 중간에 원소를 삽입하거나 삭제하는 경우에는 해당 위치 이후의 원소들을 모두 이동해야 하므로 선형 시간이 걸릴 수 있습니다.
3. 크기의 동적 조정: 벡터는 동적 배열로 구현되어 있기 때문에 원소의 개수가 증가하거나 감소할 때 크기를 동적으로 조정할 수 있습니다. 이는 배열과 달리 사전에 크기를 정해놓지 않아도 되므로 편리합니다.
4. 원소의 순서 보존: 벡터는 원소를 순서대로 저장하므로, 입력된 순서대로 원소를 유지합니다. 이는 순서가 중요한 경우에 유용합니다.
5. 메모리 오버헤드: 벡터는 동적으로 크기를 조정할 수 있지만, 크기를 조정하기 위해 추가적인 메모리 할당과 복사가 필요할 수 있습니다. 이로 인해 큰 벡터를 사용할 때 메모리 할당 및 해제 오버헤드가 발생할 수 있습니다.

책내용

벡터

동적으로 요소를 할당할 수 있는 동적 배열입니다.

중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다.

탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제, 삽입하는 데 O(n)의 시간이 걸립니다.

push_back()을 할 때 매번 크기가 증가하는 것이 아니라 공간이 꽉차면 2의 제곱승 + 1 마다 크기를 2배로 늘립니다.

ex) 1, 3, 5, 9, 17번 째에 공간을 2배 확장합니다.

※ 비용 : i번째 push_back()할 때 드는 비용, 공간이 확장 될때 마다 새로운 메모리 위치에 복사가 일어나므로 비용이 기존 들어있던 용량+1 만큼 든다.

시간 복잡도