자료구조 · 알고리즘
복잡도, 선형·트리·그래프 자료구조와 정렬·최단 경로 알고리즘
- 01
시간 복잡도와 공간 복잡도
시간·공간 복잡도의 의미와 Big-O, Big-Ω, Big-θ 표기법의 차이, Big-O를 주로 쓰는 이유를 정리한다.
- 02
재귀 함수와 꼬리 재귀 최적화
재귀 함수가 콜 스택에서 동작하는 과정과 스택 오버플로, 꼬리 재귀 최적화의 원리와 언어별 지원을 정리한다.
- 03
연결 리스트(Linked List)
연결 리스트의 구조와 배열과의 차이, 원형·이중 연결 리스트를 정리하고 파이썬으로 단순 연결 리스트를 구현한다.
- 04
스택과 큐: 원형 큐 구현과 덱
스택·큐·덱의 특징을 정리하고, 선형 큐의 빈 공간 문제를 해결하는 원형 큐를 파이썬 배열로 구현한다.
- 05
해시 테이블: 해시 함수와 충돌 처리
해시 함수 설계 방법과 로드 팩터, 체이닝·오픈 어드레싱·이중 해싱 등 해시 충돌 처리 방식을 정리한다.
- 06
트리와 이진 탐색 트리
트리와 이진 트리의 개념, 이진 탐색 트리의 탐색·삽입·중위 순회 구현과 편향 문제, 그래프와의 차이를 정리한다.
- 07
힙(Heap)과 우선순위 큐
완전 이진 트리 기반 힙의 성질과 배열 구현, 삽입·삭제 과정, 힙 정렬, 파이썬 heapq 사용법을 정리한다.
- 08
균형 이진 탐색 트리: AVL, Red-Black, B-Tree
편향 문제를 해결하는 균형 탐색 트리인 AVL 트리, 레드-블랙 트리, B-Tree의 균형 유지 방식과 쓰임새를 비교한다.
- 09
그래프: 인접 행렬과 인접 리스트
그래프의 개념과 인접 행렬·인접 리스트 구현의 장단점, 연산별 시간 복잡도 차이, 트리와의 관계를 정리한다.
- 10
최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
그래프 최단 경로 알고리즘 다섯 가지의 동작 원리와 시간 복잡도, 음수 간선과 음수 사이클에 따른 선택 기준을 정리한다.
- 11
최소 신장 트리(MST): Kruskal, Prim, Union-Find
신장 트리와 최소 신장 트리의 개념, Kruskal과 Prim 알고리즘, Union-Find로 사이클을 판별하는 방법을 정리한다.
- 12
정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
기본 정렬 알고리즘의 동작과 복잡도, 퀵 정렬과 병합 정렬의 비교, 안정 정렬, 외부 정렬, Timsort를 정리한다.
- 13
Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap
Python GIL이 thread-safe를 보장하지 못하는 이유와 Java ConcurrentHashMap, volatile을 정리한다.