Base
배열은 시작 주소와 원소 크기를 기준으로 연속 공간에 배치됩니다.
array cost
배열 메모리 비용 모델
배열의 빠른 조회와 느린 중간 변경이 어디서 오는지 메모리 배치 기준으로 정리합니다.
비용 흐름
Index
i번째 원소 주소는 base + i * size로 바로 계산됩니다.
Cache
가까운 원소를 순서대로 읽으면 캐시 지역성을 활용하기 쉽습니다.
Shift
중간 삽입과 삭제는 뒤 원소 이동 때문에 비용이 커집니다.
Prefix
반복 구간 질의는 prefix sum 같은 전처리로 조회 비용을 줄입니다.
선택 신호
O(1) Access
인덱스를 알고 자주 조회한다면 배열의 주소 계산이 강점입니다.
Insert Cost
앞이나 중간 삽입이 많으면 이동 비용이 병목이 됩니다.
Memory Locality
연속 저장은 순회 성능과 CPU 캐시에 유리합니다.
Resize
동적 배열은 용량이 모자라면 새 공간으로 복사하는 비용이 생깁니다.
Preprocess
구간 합처럼 반복 질의가 많으면 추가 배열로 시간을 줄입니다.
배열 문제는 인덱스 조회가 많은지, 중간 변경이 많은지, 반복 질의가 많은지를 먼저 표시하세요.