인덱스 조회 중심
`arr[i]` 접근과 순차 순회가 많으면 배열의 지역성이 유리합니다.
배열 조회와 수정 비용
연속 메모리, 인덱스 산술, 캐시 효율을 얻는 대신 중간 삽입, 앞 삭제, 확장 복사 비용을 별도로 계산해야 합니다.
구간 합 질의 반복
매번 선형 스캔하지 말고 누적합으로 질의 비용을 낮춥니다.
앞 삭제가 반복됨
큐처럼 쓰는 `pop(0)` 패턴은 `deque` 후보를 먼저 봅니다.
중간 수정이 빈번함
삽입과 삭제마다 원소 이동 수가 누적되어 `O(N)` 비용이 커집니다.
주소 계산
인덱스 접근은 O(1)이지만
경계 체크가 필요합니다.
이동 비용
중간 삽입 위치 뒤의 원소 수가 그대로 이동 횟수가 됩니다.
확장 복사
대량 삽입에서는 리사이즈 시점의
최악 비용을 따로
봅니다.