코딩테스트 자료구조, 알고리즘 정리

---

 

 

알아야 할 개념

시간복잡도, 공간 복잡도

 

알아야 할 자료구조

배열, 연결 리스트, 스택, 큐, 덱, 힙, 트리, 해시, 그래프

 

알아야 할 알고리즘

정렬, 구현, 재귀, 그리디, 탐색(+DFS/BFS, 백트래킹, 이분 탐색), 다이내믹 프로그래밍, 그래프 알고리즘

 

 

---

알고리즘

 

---

 

배열 문제

 

Array, LinkedList

Sliding window

Two Pointer

1차원 BFS/DFS

 

---

 

구현

 

---

 

 

재귀

 

Back Tracking

Union-Find

Divide and Conquer

 

---

 

그리디

 

---

 

정렬

 

기본 정렬 문제

Merge Sort

Quick Sort

 

---

 

탐색

 

DFS/BFS

Back Tracking

 

이분 탐색

 

Binaray Search

Parametric Search

 

---

 

다이내믹 프로그래밍

 

기본 DP

2차원 DP

최장 증가 부분 수열(LIS)

 

---

 

그래프

 

최단경로

Dijkstra

Floyd-Warshall

 

최소 신장 트리(Minimum Spanning Tree)

Kruscal

Prim

 

위상 정렬(Topology sort)

 

 

 

---