주소 계산은 O(1), 중간 이동은 O(N)이다
배열은 붙어 있는 칸 덕분에 바로 찾지만, 가운데를 바꾸는 순간 뒤 원소를 밀고 당기는 비용을 함께 계산해야 합니다.
0base
1+ 1w
2+ 2w
3+ 3w
4+ 4w
5+ 5w
`arr[i]`는 시작 주소에 `i * 원소 크기`를 더해 한 번에 위치를 계산합니다.
| 연산 | 필요한 동작 | 시간 | 실패 신호 |
|---|---|---|---|
| 인덱스 조회 | 주소 산술 한 번으로 해당 칸을 읽는다. | O(1) | 경계 체크를 빠뜨리면 오답이나 예외가 난다. |
| 맨 뒤 삽입 | 여유 칸이 있으면 끝에 바로 넣는다. | 평균 O(1) | 용량이 꽉 차면 새 공간 복사가 발생한다. |
| 중간 삽입/삭제 | 뒤 원소들을 한 칸씩 이동해 빈 칸을 만들거나 메운다. | O(N) | `pop(0)`, `insert(0)` 반복은 배열 선택 경고다. |
조회가 지배적이면 유지
반복 인덱스 조회, 정렬 후 탐색, 누적합 질의는 배열이 기본 후보입니다.
앞/중간 수정이 많으면 전환
큐라면 deque, 동적 구간 질의라면 Fenwick/세그먼트 트리를 검토합니다.
질의가 반복되면 전처리
누적합이나 차분 배열은 선형 스캔을 한 번의 조회로 바꿉니다.
판단 기준: 배열은 “찾는 비용”보다 “움직이는 원소 수”를 함께 세어야 안전합니다.