2024.12.15(일) - 2024.12.17(화)
1. DFS/BFS
DFS(Depth First Search, 깊이 우선 탐색)
시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘
Stack(스택)을 사용한다.
=> BFS에 비해 메모리 공간을 덜 차지한다.
구현 방법
1) 재귀함수를 이용한 구현
2) stack 자료 구조를 이용한 구현
활용
1) 특정 경로 찾기
2) 그래프의 모든 노드 방문
3) 경로의 특징을 저장해둬야 하는 문제
4) 그래프 사이클 여부 찾기
5) 해결책의 수가 많은 경우
BFS(Breadth First Search, 너비 우선 탐색)
시작 노드에서 인접한 노드들을 탐색하면서 너비를 우선으로 탐색하는 알고리즘
Queue(큐)를 사용한다.
구현 방법
1) queue 자료 구조를 이용한 구현
활용
1) 최단 경로 찾기
2) 최소 비용 문제
2.DP
DP(Dynamic Programming, 동적 계획법)
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하는 알고리즘 기법
답을 재활용한다.
분할 정복 알고리즘과 비슷하다.
부분 문제를 최대한 많이 이용하도록 나눈 뒤, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤(Memoization)
이를 이용하여 속도를 향상시킨다.
구현 방법
1) bottom-up
2) top-down (재귀 함수 이용)
ex) 피보나치 수열
3. 분할 정복
분할 정복(Divide and Conquer)
크고 방대한 문제를 작은 문제들로 나누어 해결한 후 다시 합치는 개념을 활용
분할 : 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눔
정복 : 가장 작은 단위의 하위 문제를 해결하여 정복
조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합
ex) Quick Sort, Merge Sort
4. 정렬
1. 선택 정렬(Selection Sort)
입력 배열 이외에 다른 추가 메모리를 요구하지 않음
첫 번째 값을 두 번째 값부터 마지막 값까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째 자리에 놓고,
두 번째 값을 세 번째 값부터 마지막 값까지 차례대로 비교하여 그 중 작은 값을 찾아 두 번째 자리에 놓는 과정을 반복하여 정렬을 수행
시간복잡도 : O(n^2)
2. 삽입 정렬(Insertion Sort)
새로운 값을 기존 정렬된 값들 사이의 올바른 자리를 찾아 삽입
대부분의 레코드가 이미 정렬되어 있는 경우 매우 효율적
레코드 수가 많고 크기가 클 경우 적합하지 않음
시간복잡도 : O(n^2) (최선의 경우 : 데이터가 모두 정렬되어 있는 경우 O(n))
3. 버블 정렬(Bubble Sort)
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
시간복잡도 : O(n^2)
4. 병합 정렬(Merge Sort)
분할 정복 알고리즘의 하나
제자리 정렬이 아니라서 임시 배열이 필요하다.
분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
정복 : 부분 배열을 정렬
조합 : 정렬된 부분 배열을 하나의 배열에 합병
시간복잡도 : O(n log n)
분할 단계 : 배열을 반으로 나누는 데 O(log n)
병합 단계 : 각 병합에서 O(n)
분할 (O(log n))
function mergeSort(arr) {
if(arr.length === 1) {
/* 더이상 분할할 수 없는 경우 */
return arr;
}
const key = Math.ceil(arr.length / 2); /* 중간 인덱스 찾기 */
const left = arr.slice(0, key);
const right = arr.slice(key);
return merge(mergeSort(left), mergeSort(right));
}
병합 (O(n))
function merge(left, right) {
const sortedArr = []; /* 임시 배열 */
while (left.length && right.length) {
/* 정렬된 두 배열 합치기, 한쪽이 길이가 0이 될 때까지 반복*/
if (left[0] <= right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
/* 반복문이 끝난 후에는 left 혹은 right 둘 중 하나만 데이터가 남아 있음 */
return [...sortedArr, ...left, ...right];
}
5. 퀵 정렬(Quick Sort)
분할 정복 알고리즘의 하나
매우 빠른 속도
배열을 비균등하게 분할한다.
pivot을 기준으로 pivot보다 작은 요소들은 모두 왼쪽으로, 큰 요소들은 모두 오른쪽으로 옮긴다.
순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(pivot)은 최종적으로 위치가 정해진다.
시간복잡도 : O(n log n)
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
const pivot = [arr[0]]; /* 중복 값이 있는 경우를 대비하여 배열로 생성 */
const left = [];
const right = [];
for(let i = 1; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else if (arr[i] > pivot) {
right.push(arr[i]);
}
else {
pivot.push(arr[i]);
}
}
/* left, pivot, right 순서로 정렬 */
return quickSort(left).concat(pivot, quickSort(right));
}
6. 힙 정렬(Heap Sort)
힙은 완전 이진 트리의 일종으로, 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조를 말함
정렬되지 않은 배열을 최대 힙이나 최소 힙으로 구성하고, 루트 노드를 가장 마지막 노드와 교환 후 힙 크기를 줄이는 방식으로 정렬
최대 힙 : 부모 노드가 자식 노드들보다 큰 값을 가져야 함
시간복잡도 : O(n log n)
힙 생성 : O(n)
제거 연산 : O(log n)
제거 연산 n 번 반복
O(n) + O(n log n) = O(n log n)
Merge Sort(병합 정렬)은 메모리가 충분하고 안정성이 필요할 때 적합하다.
Quick Sort(퀵 정렬)은 메모리가 부족하거나 빠른 정렬이 중요할 때 적합하다.
5. 이진 탐색(이분 탐색)
정렬되어 있는 데이터에서 특정한 값을 찾아내는 알고리즘
검색 범위를 절반으 줄여 나가면서 원하는 데이터를 검색한다.
function binarySearch(arr, target) {
let start = 0;
let end = arr.length - 1;
let mid;
while (start <= end) {
mid = parseInt((start + end) / 2);
if (target === arr[mid]) {
return mid;
} else if (target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
파라매트릭 서치(Parametric Search)
최적화 문제를 결정 문제로 변환하여 해결하는 기법
1) 주어진 조건에서 값이 가능한지 여부를 참/거짓으로 판별할 수 있는 함수 작성
2) 가능한 값의 최솟값과 최댓값을 기반으로 범위를 설정
3) 중간 값을 기준으로 결정 함수를 평가하며 범위를 좁혀나감
4) 탐색이 끝나면 범위의 경계값이 최적의 값이 됨
적용
- 최대 길이 구하기
- 최소 시간 구하기
6. 완전 탐색(Brute Force)
모든 경우의 수를 탐색하여 최적의 결과를 찾는 방법
최적의 해를 반드시 찾을 수 있지만, 경우의 수가 많아질수록 시간 복잡도가 증가하기 때문에 비효율적이다.
따라서, 소규모 문제에 적합하다.
완전 탐색 구현 방법
1) 재귀(DFS)
2) 반복문
3) 백트래킹
4) 순열과 조합
백트래킹
Brute Force의 비효율성을 개선한 방법
불필요한 경우를 중간에 배제하여 효율성을 높인 탐색 알고리즘
탐색 중 조건에 맞지 않는 경우에는 더 이상 진행하지 않고 되돌아가(backtrack) 다른 경로를 탐색한다.
가지치기 조건을 잘못 설정하면 성능이 저하될 수 있다.
7. 그리디
매 단계에서 가장 최적이라고 생각되는 선택을 하는 방법
최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.
이전의 선택이 이후의 선택에 영향을 주지 않는 문제들에 효율적이다.
모든 문제에서 항상 최적해를 보장하지 않으므로 그리디 알고리즘이 최적의 해를 제공할 수 있는 조건을 만족하는지 분석이 필요하다.
8. 최단 경로
1) 다익스트라(Dijkstra's Algorithm)
그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며,
음이 아닌 가중치를 가진 가중 그래프에서 사용할 수 있다.
그리디 알고리즘을 사용하여 매 단계마다 현재까지의 최단 경로를 확정짓는 방식을 사용하며,
우선순위 큐를 이용하여 효율적으로 구현할 수 있다.
시간복잡도는 O((V+E) log V)
2) 플로이드-워셜(Floyd-Warshall)
그래프에서 모든 정점 쌍 간의 최단 경로를 효율적으로 계산하는 알고리즘
동적 프로그래밍(DP)를 기반으로 하며, 가중치가 있는 그래프에서 작동한다.
음수 간선 가중치도 허용되지만, 음수 사이클이 존재하면 올바르게 작동하지 않는다.
정점의 개수가 V일 때, 시간 복잡도는 O(V^3) 이므로 정점이 많은 경우 비효율적이다.
아이디어
d[ i ][ j ] = min(d[ i ][ j ], d[ i ][ k ] + d[ k ][ j ])
3) 벨만-포드(Bellman-Ford)
단일 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
음수 간선 가중치도 허용되지만, 음수 사이클이 존재하면 올바르게 작동하지 않는다.
동적 프로그래밍(DP)를 기반으로, 최단 경로를 점진적으로 개선한다.
v-1번 반복하여 간선을 완화한다.
시간복잡도는 O(V * E)
| 알고리즘 | 다익스트라 | 플로이드-워셜 | 벨만-포드 |
| 용도 | 단일 시작점에서 다른 모든 정점까지의 최단 경로 | 모든 정점 쌍 간의 최단 경로 | 단일 시작점에서 다른 모든 정점까지의 최단 경로 |
| 음수 가중치 허용 | X | O | O |
| 음수 사이클 처리 | 감지 불가 | 감지 불가 | 감지 가능 |
| 시간 복잡도 | O((V+E) log V) | O(V^3) | O(V*E) |
| 공간 복잡도 | O(V+E) | O(V^2) 인접행렬 사용 | O(V+E) |
'알고리즘' 카테고리의 다른 글
| [알고리즘] 트리 순회 (0) | 2022.02.04 |
|---|