index로 자주 접근                 -> array / dynamic array
key 포함·대응 값을 자주 조회       -> hash set / hash map
가장 최근 값을 먼저 처리           -> stack
먼저 들어온 값을 먼저 처리         -> queue
최소·최대 우선순위를 반복해서 꺼냄  -> heap / priority queue
정렬된 key의 범위·순서가 필요       -> ordered tree/map
관계와 경로를 표현                 -> graph

연산에서 고르기

먼저 가장 자주 반복되는 연산을 적습니다. 한 번 정렬한 뒤 수십만 번 범위 조회한다면 정렬 비용을 지불할 가치가 있지만, 작은 입력에서 한 번만 찾는다면 선형 순회가 더 단순할 수 있습니다.

실제 비용

연결 리스트의 알려진 노드 삭제는 O(1)이지만 노드 탐색은 O(n)이고 cache locality가 낮을 수 있습니다. Hash table의 평균 조회는 O(1)이지만 순서가 없고 rehash 비용이 있습니다. Ordered map은 보통 O(log n)이지만 key 순회와 lower bound를 제공합니다.

자료구조의 불변 조건도 비용입니다. Heap은 root의 최솟값만 보장하고 전체 정렬을 보장하지 않으며, BST는 균형이 없으면 높이가 O(n)이 될 수 있습니다.

자주 틀리는 점

• 익숙한 자료구조를 먼저 고르고 문제를 끼워 맞추지 않습니다.
• 평균 복잡도와 최악 복잡도를 구분합니다.
• 입력 크기가 작을 때 더 복잡한 구조를 추가하지 않습니다.
• 메모리 제한과 원소당 overhead를 계산에서 빼지 않습니다.