인덱스 조회는 상수 시간
연속 메모리는 위치를 바로 계산하므로 임의 접근이 많은 문제에서 강한 후보가 됩니다.
배열 선택 비용 기준
배열은 인덱스 조회와 메모리 지역성에 강하지만, 중간 삽입과 앞삭제가 반복되면 이동 비용이 지배합니다.
삽입 뒤 원소 이동을 센다
중간 삽입과 삭제는 뒤쪽 원소를 밀거나 당기므로 반복되면 O(N) 비용이 누적됩니다.
구간 질의는 누적값 축소
조회 패턴이 반복될 때는 누적합 같은 보조 배열로 매번 선형 스캔하는 비용을 줄입니다.
배열을 유지할지 바꿀지 결정
유지임의 조회가 많고 수정이 적으면 배열의 단순성과 캐시 효율을
활용합니다.
전환앞삭제, 중간 삽입, 큐 동작이 반복되면 deque나 연결 구조를
검토합니다.
검증빈 배열, 한 원소, 끝 인덱스, 대량 삽입을 따로 실행해 경계를
확인합니다.