테마
자료구조
자료구조(data structure)는 데이터를 메모리에 어떤 모양으로 담아 둘지 정한 방법이다. 같은 데이터라도 담는 모양에 따라 찾기·넣기·지우기에 걸리는 시간이 크게 달라지므로, 코드 리뷰와 코딩 테스트, 기술면접 모두에서 "왜 이 자료구조를 골랐는가"를 설명할 수 있어야 한다.
학습 순서
- 시간 복잡도와 공간 복잡도 — 시간 복잡도(time complexity)를 빅오 표기법(Big-O notation)으로 적는 법과 대표 복잡도 비교 (면접 비중: 높음)
- 시간 복잡도와 공간 복잡도 2 — 최선·평균·최악, 분할 상환 분석(amortized analysis), 공간 복잡도(space complexity) (면접 비중: 높음)
- 배열과 연결 리스트 — 배열(array)의 인덱스 접근과 연결 리스트(linked list)의 삽입·삭제 비용 맞교환 (면접 비중: 높음)
- 배열과 연결 리스트 2 — 동적 배열(dynamic array), 연산 비용 비교, 캐시 메모리(cache memory)가 가르는 실제 성능 (면접 비중: 높음)
- 스택과 큐 — 스택(stack)의 후입선출과 큐(queue)의 선입선출, 양쪽이 열린 큐인 덱(deque)과 원형 큐(circular queue) (면접 비중: 높음)
- 해시 테이블 — 해시 함수(hash function)가 칸을 정하는 방식과 해시 충돌(hash collision) 해결 (면접 비중: 높음)
- 해시 테이블 2 — 적재율(load factor)과 재해싱(rehashing), Java
HashMap의 동작과 키 객체가 지킬equals·hashCode규약 (면접 비중: 높음) - 트리와 이진 탐색 트리 — 트리(tree) 용어, 이진 트리(binary tree)의 종류, 순회(traversal) (면접 비중: 높음)
- 트리와 이진 탐색 트리 2 — 이진 탐색 트리(binary search tree)의 연산, 균형 트리(balanced tree)와 B-Tree (면접 비중: 높음)
- 힙과 우선순위 큐 — 힙(heap)을 완전 이진 트리(complete binary tree) 모양으로 배열에 담는 법, 그리고 값을 넣고 꺼낼 때 모양을 고쳐 최댓값이나 최솟값을 항상 빨리 꺼내는 원리 (면접 비중: 중간)
- 힙과 우선순위 큐 2 — 힙 만들기와 힙 정렬(heapsort), 우선순위 큐(priority queue)의 활용 (면접 비중: 중간)
- 그래프 — 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list), BFS(Breadth-First Search, 너비 우선 탐색)·DFS(Depth-First Search, 깊이 우선 탐색) (면접 비중: 중간)
- 그래프 2 — 다익스트라 알고리즘(Dijkstra's algorithm)의 최단 경로, 위상 정렬(topological sort), MST(Minimum Spanning Tree, 최소 신장 트리) (면접 비중: 중간)