자료구조 핵심 정리 — 면접에 나오는 것만 골라서

자료구조 시간복잡도 한눈에 보기

자료구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(n)	O(n)	O(n)
동적 배열(ArrayList)	O(1)	O(n)	O(1) 평균*	O(n)
연결 리스트	O(n)	O(n)	O(1)**	O(1)**
스택/큐	O(n)	O(n)	O(1)	O(1)
해시맵	—	O(1) 평균	O(1) 평균	O(1) 평균
BST(균형)	O(log n)	O(log n)	O(log n)	O(log n)
힙	—	O(n)	O(log n)	O(log n)

* 동적 배열: 크기 초과 시 2배 확장 → 분할 상환 O(1) ** 노드 위치를 이미 알고 있을 때

배열(Array)

특징:
- 메모리 연속 할당 → 인덱스로 O(1) 접근
- 크기 고정 (정적 배열)
- 중간 삽입/삭제: 뒤 원소 전부 이동 → O(n)

면접 단골 질문:
Q: "배열과 연결 리스트의 차이는?"
A: 배열은 인덱스 접근 O(1), 삽입/삭제 O(n)
   연결 리스트는 접근 O(n), 위치 알면 삽입/삭제 O(1)
   캐시 효율은 배열이 유리 (연속 메모리)

동적 배열 (Python list, Java ArrayList):
- 내부적으로 고정 크기 배열 사용
- 꽉 차면 2배 크기 새 배열로 복사 (O(n) 비용)
- 분할 상환 분석으로 삽입은 O(1) 평균

스택(Stack)과 큐(Queue)

스택 — LIFO (Last In, First Out)
연산: push(삽입), pop(삭제), peek(최상단 조회)
사용 예: 함수 호출 스택, 괄호 유효성 검사, 되돌리기(Undo), DFS

큐 — FIFO (First In, First Out)
연산: enqueue(삽입), dequeue(삭제)
사용 예: BFS, 프린터 대기열, 메시지 큐, 캐시

덱(Deque, Double-Ended Queue):
양쪽 끝에서 삽입/삭제 모두 가능
사용 예: 슬라이딩 윈도우 최댓값 문제

면접 단골 질문:
Q: "스택 2개로 큐를 구현하라"
A: push용 스택 + pop용 스택 2개 사용
   pop 요청 시 pop 스택이 비어있으면 push 스택에서 전부 이동
   평균 시간복잡도 O(1)

해시맵(HashMap)

동작 원리:
1. 키(Key)를 해시 함수로 배열 인덱스로 변환
2. 해당 인덱스에 값(Value) 저장
3. 같은 인덱스 충돌 발생 시 해결 필요

충돌 해결 방법:
Chaining (체이닝):
  각 버킷에 연결 리스트 연결
  최악: 모두 같은 버킷 → O(n)
  평균: O(1), 부하율 < 0.75 유지

Open Addressing (개방 주소법):
  충돌 시 다음 빈 버킷 탐색
  Linear Probing: 한 칸씩 이동 (군집화 문제)
  Quadratic Probing: 거듭제곱 간격 이동
  Double Hashing: 두 번째 해시 함수로 간격 결정

면접 단골 질문:
Q: "해시맵의 시간복잡도가 O(1)인 이유는?"
A: 좋은 해시 함수와 낮은 부하율(load factor) 유지 시
   충돌이 거의 없어 평균적으로 O(1) 달성
   최악(모든 키가 충돌)은 O(n)

연결 리스트(Linked List)

단일 연결 리스트: Node(data, next)
이중 연결 리스트: Node(data, prev, next) → 양방향 탐색

장점: 중간 삽입/삭제 O(1) (노드 위치 알 때), 동적 크기
단점: 인덱스 접근 O(n), 포인터 저장 공간 추가, 캐시 비효율

면접 단골 질문:
Q: "연결 리스트에서 사이클을 감지하는 방법은?"
A: Floyd 알고리즘 (토끼와 거북이)
   slow 포인터: 1칸씩, fast 포인터: 2칸씩 이동
   두 포인터가 만나면 사이클 존재
   시간복잡도 O(n), 공간복잡도 O(1)

Q: "연결 리스트를 뒤집는 방법은?"
A: prev, curr, next 3개 포인터로 방향 전환
   시간복잡도 O(n), 공간복잡도 O(1)

트리(Tree)와 이진 탐색 트리(BST)

트리 용어:
루트(Root): 최상위 노드
리프(Leaf): 자식 없는 노드
높이(Height): 루트에서 최대 깊이
깊이(Depth): 루트에서 특정 노드까지 거리

이진 탐색 트리(BST):
- 왼쪽 자식 < 부모 < 오른쪽 자식
- 탐색/삽입/삭제: O(log n) 평균, O(n) 최악(편향 트리)

균형 BST (AVL 트리, Red-Black 트리):
- 높이를 O(log n)으로 보장
- Java TreeMap, C++ std::map이 Red-Black 트리 기반

힙(Heap):
- 완전 이진 트리, 부모가 자식보다 크거나 작음
- 최대/최솟값 추출 O(log n)
- 우선순위 큐 구현에 사용

면접 단골 질문:
Q: "BST의 중위 순회(Inorder) 결과는?"
A: 왼쪽 → 루트 → 오른쪽 순 방문
   BST에서 중위 순회 = 정렬된 순서로 출력

그래프(Graph)

표현 방법:

인접 행렬 (Adjacency Matrix):
V x V 2차원 배열, 연결: 1, 미연결: 0
공간: O(V^2), 간선 확인: O(1)
적합: 정점 수 적고 간선 많을 때(밀집 그래프)

인접 리스트 (Adjacency List):
각 정점마다 연결된 정점 리스트
공간: O(V+E), 간선 확인: O(degree)
적합: 정점 많고 간선 적을 때(희소 그래프)

면접 단골 질문:
Q: "BFS와 DFS의 차이는?"
A: BFS(너비 우선): 큐 사용, 최단 경로 보장
   DFS(깊이 우선): 스택/재귀 사용, 경로 탐색, 사이클 감지
   시간복잡도 둘 다 O(V+E)

관련 검색어  ·  자료구조 면접, 해시맵 충돌 해결, BST 시간복잡도, 연결 리스트 사이클, BFS DFS 차이, 스택 큐 차이, 개발자 면접 자료구조