0. 개요
지금 까지 정리해온 내용들이 빛을 발할 때이다. 알고리즘 패러다임이란 알고리즘 접근 패턴을 뜻한다. 한 문제에 여러가지 방식의 풀이가 있듯이 마찬가지로 한 문제에 두 개 이상의 알고리즘 패러다임이 존재할 수도 있는 것이다.
1. Brute Forece
- 무식한 힘, 하나부터 열까지 전부다 계산해서 찾는 방식, 인풋이 적은 경우에만 사용
- 종류
- 합병 정렬
- 퀵 정렬
2. Backtracking
- 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아 감. 최적화 문제와 결정 문제를 푸는 방법
- DFS,BFS으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어 답이 절대로될 수 없는 상황을 정의하고, 그렇나 상황일 경우에는 탐색을 중지시킨뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색
3. DP,Dynamic Programming(동적계획법)
- 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
- 최단 경로 문제, 행렬의 제곱 문제등의 최적화에 사용된다.(벨만-포드 알고리즘)
- 조건
큰 문제를 작은 문제로 나눌 수 있어야 한다.
최적의 해를 찾는 구조를 만들 수 있어야 한다.
작은 문제들이 중복되어야 한다.분할 정복 알고리즘의 분할된 작은 문제들은 서로 독립적, DP에선 해결된 문제들을 서로 공유
4. Greedy Algorithm
- DP 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘
- 선택절차, 적절성 검사, 해답 검사를 거친다.
- 조건
탐욕적 선택 속성: 이전 선택이 이후의 선택에 영향을 주지 않아야함
최적 부분 구조: 문제애 대한 최종 해결방법은 부분문제에 대한 최적 문제해결방법으로 구성
5. Kruskal Algorithm(크루스칼 알고리즘)
-
모든 정점들을 가장 적은 비용으로 연결하기 위해 사용
-
최소신장트리를 구하기 위한 알고리즘
신장트리: 그래프에서 모든 정점을 포함하고, 정점 간 서로 연결이 되며 싸이클이 존재하지 않는(tree의 기본 조건) 그래프
-
신장 트리는 정점의 개수가 n개일 때, 간선이 n-1개
-
이런 신장 트리 중 가중치의 합이 최소가 되는 신장트리가 최소 신장트리(MST, Minimum Spannig Tree)
-
크루스칼 알고리즘은 그리디 알고리즘의 일종
6. 추가적으로
Union find, 네트워크 흐름 알고리즘 등 여러 알고리즘이 있다. 개념 정리는 이정도로 하고 이제 문제를 통해 배워보는 것이 좋겠다.
Reference
좋은 지식 나누어요