알고리즘 모음집

2024-02-14 기준

Greedy

 Minimum Spanning Tree (MST)
 Shortest Path
 Deadline Scheduling / Tape Storage

---

Divide and Conquer

 Merge Sort / Quick Sort
 Closest Pair
 Convex Hull
 Matrix Multiplication / Karatsuba Algorithm

---

Dynamic Programming

 Fibonacci Number
 Select Working Days
 Matrix Multiplication
 Maximum Subarray
 All-Pairs Shortest Path
 근사 문자열 매칭과 거리함수
 최장 공통 부분 서열 (LCS)
 Sequence Alignment
 최대 공백 정사각형, 최대 공백 직사각형
 금화 모으기, 동전 거스름 돈
 Longest Increasing Subsequence (LIS)
 완전 정보 게임 (NIM 게임), 돌 가져가기

---

Graph

 Graph Traversal
 DFS
 Bipartite Graph Detection
 Cut Vertex, Cut Edge
 BCC
 Topological Sort
 SCC

---

Back Tracking

 N-Queen

---

Pseudo Polynomial

 동전 문제, 막대기 자르기, 합 분해

---

State Space

 15 Puzzle, Subset Sum Problem
 Traveling Salesman Problem

---

Randomized Algorithm

 Randomized QuickSort
 Linked List in an Array (Las Vegas)
 Primality Test (Monte Carlo)
 Lowest Common Ancestor
 Boruvka’s MST Algorithm, Randomized MST