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
- Divide : 초기 배열을 2개의 배열로 분할
- Conquer : 각 부분 배열을 정렬
- Combine : 부분 배열을 하나의 배열로 결합
4. MST (Minimum Spanning Tree)
- Prim Algorithm : 정점을 선택하고 그것과 연결된 가장 적은 비용의 정점을 선택 (ElogV)
- Kruskal Algorithm : 모든 간선에 대하여 가장 비용이 적은 간선을 선택 (ElogE)
프림 알고리즘은 정점의 개수에 비해 간선이 많이 주어진 경우 선택, 크루스칼은 간선의 개수에 비해 정점이 많이 주어진 경우
5. Prim Algorithm
- 시작 단계에서는 시작 정점만이 MST 집합에 포함
- 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장, 즉 가장 낮은 가중치를 먼저 선택
- 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복
6. Kruskal Algorithm
- 그래프의 간선들을 가중치의 오름차순으로 정렬
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택 (Union_find)
- 해당 간선을 현재의 MST의 집합에 추가
7. 최단 경로를 구하기 위한 알고리즘
- Dijkstra : 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구함
- Bellman-Ford : 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구함 + 가중치가 음수일 때도 사용이 가능 (음의 사이클 검사 가능)
- Floyd-Warshall : 모든 정점 ~ 모든 정점까지의 최단 경로
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개의 간선을 확인 - 이 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가짐
- 따라서 총
V x E번 연산하므로O(VE)의 시간복잡도를 가짐
10. Floyd-Warshall Algorithm
- 사이클이 없다면 음수 가중치를 가져도 적용 가능
- DP 로 접근
- 모든 가능한 경유지에 대해서 모든 정점 -> 모든 정점으로 가는 최단 거리를 확인하므로
O(V^3)의 시간복잡도를 가짐
