자료구조 선택 비용 비교

주요 연산 표시

문제에서 가장 많이 반복되는 연산이 검색인지 삽입인지 삭제인지 먼저 표시한다.

가끔 하는 연산보다 반복되는 연산이 중요하다

인덱스로 바로 접근해야 하는지, 앞에서부터 순서대로 처리하면 되는지 나눈다.

배열과 리스트의 큰 차이다

입력 순서, 정렬 순서, 우선순위, LIFO/FIFO 규칙이 필요한지 본다.

규칙이 자료구조를 고른다

연속 메모리 재할당, 포인터 오버헤드, 해시 충돌, 트리 균형 비용을 비교한다.

빅오만으로 끝나지 않는다

평균 O(1)과 최악 O(n), 균형 트리와 편향 트리의 차이를 문제 조건과 맞춘다.

시험은 최악 조건을 자주 묻는다

Array

임의 접근과 순회 index 접근이 빠르고 메모리 locality가 좋지만 중간 삽입 삭제가 비싸다.

크기 변경 비용을 본다

Linked List

노드 연결 변경 위치를 알고 있으면 삽입 삭제가 쉽지만 탐색과 메모리 locality가 약하다.

포인터 오버헤드가 있다

Stack/Queue

처리 순서 제약 LIFO와 FIFO 규칙이 문제 조건과 직접 맞을 때 사용한다.

괄호 검사와 BFS를 연결한다

Hash/Tree

검색 구조 해시는 평균 빠른 조회, 트리는 정렬 순서와 범위 탐색에 강하다.

충돌과 균형 조건을 확인한다

빈도 표시 가장 많이 실행되는 연산을 문제 지문에서 표시한다.

최악 조건 평균 시간복잡도만 말하지 않고 최악 조건을 함께 확인한다.

순서 요구 정렬, FIFO, LIFO, 우선순위가 답의 핵심인지 본다.