내일배움캠프 12일차 - 자료구조 & 알고리즘 2주차 : 데이터를 담는 그릇
vector
C스타일 배열(int arr[10])은 크기가 고정이다. 선언할 때 크기를 정하면 나중에 늘릴 수 없다.
→ vector는 이 문제를 해결하는 동적 배열이다.
- size: 실제 들어있는 원소 개수 ("가방에 든 아이템 수")
- capacity: 현재 확보된 메모리 공간 ("가방의 전체 칸 수")
vector 재할당의 동작원리
capacity 4, size4인 vector에 push_back(5) 호출
2) 기존 원소를 새 공간으로 복사
3) 기존 메모리 해제 + 새 원소 추가
재할당 = O(n) 복사 비용 → push_back의 숨은 비용
※ 복사할 때 원소를 하나하나 옮겨야 하기 때문이다.
왜 2배씩 늘릴까?
→ 2배씩 늘리면 재할당 횟수가 log n번으로 줄어듦
push_back은 평균 O(1)
이것을 분할 상환 분석(Amortized Analysis)이라고 한다.
미리 크기를 안다면 reserve(n)으로 재할당 자체를 방지할 수 있다.
vector 연산별 시간 복잡도
pop_back(): O(1) < 마지막 원소만 제거 >
v[i]: O(1) < 연속 메모리, 바로 접근 >
insert(중간): O(n) < 삽입한 칸 뒤의 원소를 전부 밀어야함(비용발생) >
erase(중간): O(n) < 제거한 칸 뒤의 원소를 전부 당겨야함(비용발생) >
※ insert, erase를 반복문 안에서 매번 호출하면 O(n)×n = O(n^2)
순회 방법 비교
1) 인덱스 for문 (인덱스가 필요할때)
: for (int i = 0; i < v.size(); i++)
2) 범위 기반 for (향상된 for문, 읽기만 할 때)
: for (int x : v) ← 정적배열에도 사용가능
3) 범위 기반 + 참조 (원소를 수정할 때)
: for (int& x : v)
vector는 힙에 한줄로 저장된다.
 |
| 정적배열과 vector의 스택메모리, 힙메모리 구조 |
스택(Stack) = 함수 호출 시 자동으로 잡히는 작은 공간(data ptr, size, capacity 정보 등)
힙(Heap) = 프로그래머가 요청해서 잡는 넓은 공간
캐시 히트 vs 캐시미스
: 기본적으로 주변에 있는 것들도 같이 쓸 확률이 높으므로
캐시 히트(Cache hit): vector처럼 데이터가 연속적으로 붙어있으면 → 빠름!
캐시 미스(Cache miss): Linked List처럼 데이터가 산발적으로 흩어져 있으면 → 느림
→ 시작 주소 + i * sizeof(원소) = 덧셈 한번
게임·웹·데이터베이스의 사례
1) 게임 개발
: 몬스터 목록, 총알 리스트, 파티클 배열
→ 매 프레임 순회하며 업데이트. 캐시 효율이 핵심
UE5에서도 TArray = vector와 동일 구조
2) 웹/서버
: 사용자 목록, 상품 리스트
→ vector에 담아 처리
페이지네이션(20개씩 끊기)도 인덱스 접근 O(1) 덕분
3)일반 CS
: Python list, Java ArrayList = 전부 같은 원리
"배열의 인덱스 접근이 O(1)인 이유" = 연속 메모리 (시작주소 + i번째 칸 → 덧셈)
오늘의 핵심
- vector는 연속 메모리에 데이터를 담는 동적 배열
- 뒤에 추가/삭제는 O(1), 중간 삽입/삭제는 O(n)
- capacity가 부족하면 2배로 재할당, 비용을 줄이려면 reserve() 사용
- 연속 메모리 → 캐시 효율이 좋음: 순회가 빈번한 상황에 가장 적합
※ 시간복잡도 팁
맨 앞 원소를 삭제하는 erase(v.begin())을 100번 반복하면
총 시작 복잡도는?
정답: O(n)
설명: O(100n) = 사실상 O(n)
100번은 상수이므로 O(100*n) = O(n)
하지만 n번 반복하면 O(n)*n=O(n^2)
상수 vs 변수의 차이가 핵심
댓글
댓글 쓰기