배열

1. 정적 배열 (Static Array): 고정된 크기를 가진 배열
2. 동적 배열 (Dynamic Array): 가변적인 크기를 가진 배열

정적 배열

• 고정된 크기의 저장 공간
• 순차적으로 메모리에 저장됨
• 인덱스를 통해 빠르게 원소 접근 가능 (O(1))
• 크기 변경 불가능 (컴파일 시 크기 고정)

동적 배열 (vector)

• 가변 크기의 저장 공간 (필요 시 자동으로 메모리 재할당)
• 인덱스를 통한 원소 접근 가능 (O(1))
• 새로운 배열을 생성해 복사 및 확장 필요 (resize 시)

❓ Q. 배열(vector)은 중간에 비어 있을 수 있나?

A. 아니요.vector에서 원소를 제거하면 뒤의 원소들이 자동으로 앞으로 당겨져, 중간에 빈 칸 없이 연속적인 구조가 유지됨.

---

정적 배열 vs 동적 배열 비교

기능	시간 복잡도	정적 배열 (int arr[])	동적 배열 (vector<int>)
원소 접근	O(1)	arr[i] (인덱스)	v[인덱스], v.at(인덱스)
길이 확인	O(1)	컴파일 시 고정	v.size()
맨 뒤 삽입	O(1)	불가	v.push_back(값)
맨 뒤 삭제	O(1)	불가	v.pop_back()
중간 삽입	O(n)	구현	v.insert(반복자, 값)
중간 삭제	O(n)	구현	v.erase(반복자)
배열 복사	O(n)	memcpy, for문 등	vector<int> v2 = v1;

❗️중간 삽입/삭제가 빈번한 경우, 더 적합한 자료구조로 변경해야함

상황	추천 자료구조	이유
중간 삽입/삭제 많음	list (C++ STL)	포인터 연결 기반이므로 중간 삽입/삭제 O(1) 성능을 제공
특정 값 탐색 + 삭제	unordered_set or unordered_map	탐색 + 삭제 평균 O(1) (해시 기반)
정렬된 상태 유지 + 중간 삽입/삭제	set, map (balanced BST)	자동 정렬, 탐색/삽입/삭제 O(log n) 성능을 제공

기타 자주쓰는 함수 (vector<int> 기준)

함수	설명	시간 복잡도
*sort(반복자, 반복자)	전체 정렬 (오름차순 기본)	O(n log n)
*reverse(반복자, 반복자)	전체를 역순으로 정렬	O(n)
front() / back()	첫/마지막 원소 반환	O(1)
empty()	비어있는지 확인	O(1)
swap(v2)	두 벡터 내용 교환	O(1)
begin() / end()	첫/끝 원소 반복자 반환	O(1)
rbegin() / rend()	역방향 반복자 반환 (뒤에서부터 순회)	O(1)

*algorithm 헤더 필요