1. DFS/BFS 장단점
BFS 장점
: 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장
최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음
노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리
BFS 단점
: 재귀 호출을 사용하는 DFS와는 달리 큐를 이용해 다음에 탐색할 노드를 저장하기 때문에 노드가 많을 수록 필요없는 노드들까지 저장해야하기 때문에 저장공간 필요
노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아지기 때문에 비현실적
DFS 장점
: BFS에 비해 저장공간의 필요성이 적고 백트래킹을 해야하는 노드들만 저장해주면 됨
찾아야 하는 노드가 깊은 단계에 있을 수록, 그 노드가 좌측에 있을 수록 BFS보다 유리
DFS 단점
: 답이 아닌 경로가 매우 깊다면, 그 경로에 빠질 우려가 있음
내가 지금까지 찾은 최단경로가 끝까지 탐색했을 때 최단 경로가 된다는 보장이 없음
2. Quick Sort
라이브러리 없이 정렬을 구현하려고 할 때 quick sort
로 구현하는 것이 가장 성능적으로 좋다. 퀵 소트는 average case
에서 nlogn
의 시간 복잡도를 가짐
worst case
가 나타날 경우 n^2
의 시간 복잡도를 가지게 되는데 피벗의 위치를 다르게 설정함으로써 시간 복잡도를 개선시킬 수 있음 -> 일정한 위치에 대해서만 피벗을 설정하는 것보다 무작위로 선택한다거나 첫 번째, 가운데, 마지막 element중 중간값을 계산하여 피벗을 설정했을 때 시간 복잡도를 더 개선시킬 수 있음
3. Merge Sort
4. MST (Minimum Spanning Tree)
프림 알고리즘은 정점의 개수에 비해 간선이 많이 주어진 경우 선택, 크루스칼은 간선의 개수에 비해 정점이 많이 주어진 경우
5. Prim Algorithm
6. Kruskal Algorithm
7. 최단 경로를 구하기 위한 알고리즘
8. Dijkstra Algorithm
방법 1
출발 노드 S
에서 모든 노드들까지의 최단 거리를 저장하는 배열 D
를 초기화
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (D배열 검사)
선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 배열 D를 갱신
모든 노드를 방문할 때까지 반복
노드의 개수를 V라고 할 때, O(V^2)
의 시간복잡도
방법 2 (Heap, Priority queue)
출발 노드 S에 대하여 D 배열을 초기화할 때 D[S]=0
을 해주는 동시에 힙에 (S,0)
을 넣어줌
힙에서 맨 위에 있는 노드 I
를 꺼냄
만일 꺼낸 노드 I
의 거리 정보가 현재 D[I]
보다 크다면 이미 방문한 노드일 것이므로 무시
I를 대상으로 Dijkstra algorithm 수행, D 배열이 갱신될 경우
그 노드 정보를 힙
에 넣음
힙에 노드가 없을 때까지 반복
노드의 개수를 V, 간선의 개수를 E라고 할 때 O(ElogV)
=> 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하는 과정이 있는데 이 과정에서 O(V)
만큼의 비용이 발생한다. 하지만 힙을 사용할 경우 O(log {힙에 저장한 노드의 개수})
로 줄일 수 있음
9. Bellman-Ford Algorithm
V-1
번 E개
의 모든 간선을 확인V번 째 E개
의 간선을 확인V x E
번 연산하므로 O(VE)
의 시간복잡도를 가짐Floyd-Warshall Algorithm
O(V^3)
의 시간복잡도를 가짐