[알고리즘_1] 알고리즘 분류

개론

개념을 분류하는 것을 좋아한다. 알고리즘을 명확한 기준을 가지고 분류하기는 어렵지만, 내 기준으로 정리해보았다. 기본적인 알고리즘은 왠만하면 포함하지만, 어려운 알고리즘들은 내가 공부했거나 공부할 예정인 알고리즘들만 포함되어있다.

알고리즘 분류

1. 탐색 및 정렬

• Brute Force : 모든 가능한 경우를 시도하는 방법
• Depth First Search (DFS) : 깊이를 우선적으로 탐색하는 방법
• Breadth First Search (BFS) : 너비를 우선적으로 탐색하는 방법
• Topological Sort : Directed Acyclic Graph (DAG)에서 노드를 순서대로 정렬하는 알고리즘

2. 최적화 기법

• Greedy : 현재 상황에서 가장 좋아보이는 선택을 하는 방법
• Dynamic Programming (DP) : 문제를 작은 하위 문제로 나누어 푸는 방법
  • Longest Common Subsequence (LCS) : 두 문자열의 가장 긴 공통 부분 수열을 찾는 알고리즘
  • Longest Increasing Subsequence (LIS) : 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘
• Knapsack : 물건을 배낭에 담을 때 가치를 최대화 하는 방법을 찾는 문제

3. 그래프 알고리즘

• Dijkstra : 가중치가 있는 그래프에서 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
• Floyd-Warshall : 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘
• Union-Find : 여러 노드가 서로 연결되어 있는지를 판별하는 자료구조
• Strongly Connected Component (SCC) : 방향 그래프에서 순환할 수 있는 노드들을 찾는 알고리즘
  • SAT-2 : 2-Satisfiability 문제

4. 자료구조

• Segment Tree : 배열에서 구간에 대한 정보를 저장하는 자료구조

5. 문자열 알고리즘

• Knuth-Morris-Pratt (KMP) : 부분 문자열을 효율적으로 찾는 문자열 검색 알고리즘
• Aho-Corasick : 여러 문자열을 동시에 검색하기 위한 알고리즘

6. 수학 및 수치 해석

• Fast Fourier Transform (FFT) : Convolution 연산을 빠르게 수행하는 알고리즘

공부 계획

• 다익스트라 -> 플로이드-워셜 -> 벨만-포드
• 위상정렬 -> Union-Find -> SCC, SAT
• 세그먼트 트리
• KMP -> 아호-코라식
• FFT -> NTT