연산 빈도와 비용

반복되는 질문 탐색

문제가 계속 묻는 것이 존재 여부인지, 최소값인지, 구간 합인지에 따라 구조가 바뀐다.

O(1), O(log n), O(n)을 연산 횟수와 곱해 시간 제한 안에 드는지 계산한다.

정렬 유지가 필요한지, 원래 순서가 필요한지, 중복을 세야 하는지에 따라 구조를 결정한다.

Array

인덱스 접근 순서와 위치가 중요하고 연속 순회가 많을 때 강하다.

중간 삽입은 비싸다.

Hash

빠른 존재 확인 평균 O(1) 조회가 필요할 때 유용하다.

충돌과 메모리 비용이 있다.

Heap

최솟값/최댓값 반복 전체 정렬 없이 현재 우선순위만 꺼낸다.

임의 삭제는 별도 처리한다.

Graph

관계 탐색 정점과 간선으로 상태 전이를 모델링한다.

방문 표시가 핵심이다.

연산 카운트 가장 많이 반복되는 동작이 무엇인지 숫자로 적었는가.

중복 같은 값이 여러 번 나올 때 set, map, count 중 무엇이 필요한가.

순서 입력 순서, 정렬 순서, 우선순위 중 어떤 순서가 답에 영향을 주는가.

// many membership queries -> unordered_set
// repeated min extraction -> priority_queue
// range sum updates -> Fenwick or segment tree