랜덤 조회 반복
arr[i]가 대부분이면 연속 메모리와 O(1) 접근을 그대로
활용한다.
배열 선택 기준
인덱스 접근의 장점과 중간 삽입/삭제의 이동 비용을 연산 분포로 비교하면 자료구조 선택이 명확해집니다.
입력 분포
N
100,000
Q
100,000 operations
연산 비율
조회, 앞삭제, 구간질의 비율
구간 합 질의
배열을 유지하되 누적합을 더해 각 질의를 O(1)로 낮춘다.
앞 삭제 반복
pop(0)가 많으면 매번 전체를 당기므로 덱으로 바꾼다.
조회와 갱신 혼합
갱신+구간 질의면 Fenwick/세그먼트 트리를 본다.
조회 90%
인덱스 접근과 순회가 대부분이면 배열이 가장 단순하고 빠르다.
정렬, 이분 탐색, 누적합과 잘 맞는다.
앞 삭제 반복
파이썬 리스트의 pop(0)는 뒤 원소 이동으로 O(N)이
누적된다.
큐는 deque를 우선 검토한다.
중간 삽입 다수
삽입 위치 뒤 원소가 계속 밀리면 평균이 아니라 총 이동량이 병목이 된다.
작업 자체를 배치 처리할 수 있는지 본다.
구간 업데이트
여러 구간에 값을 더한 뒤 한 번에 결과를 보면 차분 배열이 적합하다.
업데이트 후 질의가 섞이면 트리를 쓴다.