반복 조회가 많으면 한 번의 조회 비용부터 줄인다.
selection matrix
자료구조는 이름이 아니라 요구 연산으로 고른다
조회, 순서, 최솟값, 연결 관계 중 가장 자주 묻는 연산을 먼저 고르면 후보가 빠르게 좁혀진다.
연산
후보
위험 신호
요구 연산을 후보 자료구조로 바꾸기
| 문제 신호 | 핵심 연산 | 우선 후보 | 버릴 후보 |
|---|---|---|---|
| 존재 여부, 빈도 | 키로 빠르게 찾는다 | Set / Map | 매번 선형 탐색 |
| 정렬·구간 처리 | 순서를 보존하며 훑는다 | Array / List | 무작정 Hash |
| 최소·최대 반복 | 가장 작은/큰 값을 계속 꺼낸다 | Heap | 정렬을 매번 다시 수행 |
| 경로·도달 가능성 | 노드와 간선으로 이동한다 | Graph | 배열 인덱스만 고집 |
중복 허용, 순서 보존, 정렬 유지 여부를 분리한다.
삽입/삭제가 중간에서 자주 일어나면 배열 이동 비용을 본다.
자료구조를 바꾼 뒤에도 같은 반례를 다시 돌린다.