Array Cost Model

배열 성능: 주소 계산과 이동 비용의 교환

연속 메모리 덕분에 `arr[i]`는 빠르지만, 중간 위치를 바꾸는 순간 뒤 원소 이동이 누적되어 병목이 됩니다.

0base
1+1w
2+2w
3+3w
4+4w
5+5w

인덱스 `i`는 시작 주소에 원소 크기 `w`를 곱해 바로 위치를 계산합니다.

O(1)

인덱스 조회

주소 계산 한 번으로 접근합니다. 랜덤 조회와 반복 질의에서 배열의 장점이 가장 크게 드러납니다.

O(N)

중간 삽입/삭제

빈 칸을 만들거나 메우기 위해 뒤 원소들을 밀고 당겨야 하므로 입력이 커질수록 비용이 선형으로 늘어납니다.

resize

확장과 복사

용량이 부족하면 더 큰 공간을 잡고 기존 값을 복사합니다. 평균은 괜찮아도 순간 비용을 고려해야 합니다.

배열 선택 전 점검

조회가 지배적인가 반복 `arr[i]`, 정렬 후 탐색, 누적합 질의라면 배열이 기본 후보입니다.
앞/중간 수정이 많은가 `insert(0)`, `pop(0)`, 중간 삭제가 반복되면 이동 비용을 먼저 계산합니다.
전처리로 바꿀 수 있는가 누적합, 차분 배열, 슬라이딩 윈도우는 배열을 문제 해결 도구로 바꿉니다.
대체 구조가 필요한가 양끝 수정은 덱, 동적 구간 질의는 Fenwick이나 세그먼트 트리를 검토합니다.