배열과 벡터 (Array & Vector)

6 Mar 2026 • munjjang9

저번 포스트 요약 — 시간복잡도

시간 복잡도는 코드가 동작할 때 연산 횟수가 증가하는 비율의 척도를 나타낸 것이고, 빅오 표기법을 통해 표현한다.
빅오 표기법은 입력의 수가 n만큼 커질 때 연산 횟수가 얼마나 늘어나는지를 나타낸다.
O(1) ~ O(n!)까지 다양한 표기법이 존재하며, 상황에 따라 특정 시간이 더 빠른 경우도 존재한다.

배열과 벡터의 차이

배열

고정 크기로 선언된다. 선언 당시에 크기가 결정되며, 변경이 불가능하다.
메모리에 값을 연속적으로 저장한다.
인덱스 접근 시에 O(1)의 시간 복잡도를 가진다.

벡터

고정 크기가 아닌, 동적으로 크기가 조절된다. 런타임에 크기 변경이 가능하다.
배열과 동일하게 메모리에 값을 연속적으로 저장한다.
역시 인덱스 접근 시에 O(1)의 시간 복잡도를 가진다.

벡터의 내부 동작

처음 할당한 크기의 메모리가 다 채워지면, 용량을 2배로 늘린다.
대부분의 push_back 동작은 O(1)의 시간 복잡도를 가지지만, 평균적으로 Amortized O(1)의 시간 복잡도를 가진다.(위의 이유 때문이다.)

size() vs capacity()

size는 벡터 안의 실제 원소의 개수를 리턴한다.

capacity는 할당된 메모리의 크기를 리턴한다.

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

v.size();     //3
v.capacity(); //4

v.push_back(4);
v.push_back(5);

v.size();     //5
v.capacity(); //8

주요 연산 시간복잡도

연산	시간복잡도
접근	O(1)
push_back	Amortized O(1)
pop_back	O(1)
중간 삽입/삭제	O(n)
탐색	O(n)

중간 삽입/삭제가 O(n)인 이유는 중간에 삽입 또는 삭제하는 경우에 뒤에 있는 원소들을 한 칸씩 밀거나 당겨야 하기 때문이다.

마치며

게임 프로그래밍을 하면서 배열은 진짜 어마무시하게 사용한 것 같다.
벡터는 DX를 공부할 때를 제외하면 거의 안 쓰기는 했지만, 유니티 C#의 List나 언리얼 C++의 TArray와 비슷한 것 같다.
코딩을 한다면 배열과 벡터의 개념은 자주, 많이 쓰기 때문에 꼭 숙지해놔야겠다.