개발
[알고리즘] 개발자가 알아야 할 핵심 알고리즘 10선 (공유용)
1. 정렬 (Sorting)
Quick Sort: 피벗을 기준으로 작은 값과 큰 값을 나누어 재귀적으로 정렬하는 방식. 평균 시간복잡도 O(n log n).
Merge Sort: 리스트를 반으로 나누고 정렬한 후 합치는 방식. 안정 정렬이며, 항상 O(n log n)의 시간복잡도.
2. 탐색 (Searching)
이진 탐색 (Binary Search): 정렬된 배열에서 중간값과 비교하며 절반씩 줄여가는 방식. 시간복잡도 O(log n).
3. 그래프 (Graph)
DFS (Depth-First Search): 깊이 우선 탐색으로, 한 방향으로 끝까지 탐색 후 백트래킹.
BFS (Breadth-First Search): 너비 우선 탐색으로, 가까운 노드부터 차례대로 탐색.
4. 최단 경로 (Shortest Path)
Dijkstra: 가중치가 양수인 그래프에서 시작점으로부터 최단 경로를 구함.
Floyd-Warshall: 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘. O(n³).
5. 그리디 (Greedy)
현재 단계에서 가장 좋은 선택을 반복하여 최적해를 구함.
예시: Activity Selection, 동전 거스름돈 문제 등.
6. 동적 계획법 (Dynamic Programming)
중복되는 부분 문제를 메모이제이션(기억)하여 계산을 줄이는 방식.
Fibonacci 수열, Knapsack(배낭 문제) 등에서 활용.
7. 분할 정복 (Divide and Conquer)
문제를 나누고 각각 해결한 뒤, 병합하여 전체 문제를 푸는 방식.
Merge Sort, Karatsuba 곱셈 알고리즘 등.
8. 백트래킹 (Backtracking)
가능한 모든 경우를 재귀적으로 시도하되, 조건을 만족하지 않으면 가지를 쳐서 탐색을 줄이는 방식.
N-Queen, 순열 생성 문제 등.
9. 트리 & 힙 (Tree & Heap)
Segment Tree: 구간합, 구간최대/최소 등을 빠르게 계산하는 트리 자료구조.
Heap: 우선순위 큐 구현에 사용. 최소/최대값을 빠르게 찾음.
10. 수학 (Mathematics)
에라토스테네스의 체: 소수를 빠르게 구하는 방법.
GCD(최대공약수), 유클리드 호제법: 수의 최대공약수 구하기.
다양한 수학 기반 알고리즘이 코테 문제에 자주 등장.
출처