DongDD's IT

Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall Algorithm - 그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘- 다익스트라 알고리즘을 모든 정점에서 수행한 것과 같은 알고리즘이지만 플로이드 와샬 알고리즘은 구현이 간단하다.- 음수 가중치에 대한 처리가 어려운 다익스트라 알고리즘에 비해 플로이드 와샬 알고리즘은 사이클이 없는 경우 음수 가중치 처리가 가능하다. Floyd-Warshall Complexity - 단순히 반복문 3개를 vertex만큼 돌기 때문에 O(V^3)의 시간 복잡도를 갖는다.- 특정 정점에서 특정 정점까지의 경로를 저장해나가며 구한 경로를 이용해 새로운 최단 경로를 찾는 DP방식으로 수행된다. 그러므로 2차원 배열이 필요하므로 O(V^..

BFS(Breadth-First-Search) Algorithm BFS Algorithm - 그래프나 트리같은 자료구조에서 사용하는 Search 알고리즘- DFS에서는 재귀 호출로 구현하는 경우가 많지만, BFS에서는 보통 queue 자료구조를 사용해 구현한다.- 갈 수 있는 경로를 쭉 따라가는 DFS와 달리, 현재 Vertex에서 갈 수 있는 모든 정점을 방문한 후 방문한 정점을 기준으로 다시 갈 수 있는 모든 정점을 방문하는 식으로 진행된다. BFS Complexity - 인접 리스트를 이용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우에 따라 시간복잡도가 다름 1) 인접 리스트- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 가진..

DFS(Depth-First-Search) Algorithm DFS Algorithm- 그래프나 트리같은 자료구조에서 탐색을 할 때 사용하는 알고리즘 중 하나- DFS는 구현 방식이 여러가지 있고 각각으 시간 복잡도는 다름- 하나의 정점부터 가장 깊이가 깊은 곳까지 탐색하며 방문하지 않은 모든 정점들을 탐색함 DFS Complexity- 인접 리스트를 사용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우 시간복잡도가 다름 1) 인접 리스트- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 갖는다. 2) 인접 행렬- 방문할 정점을 찾을 때 연결된 모든 정점을 순회하며 이어져 있는지 체크를 해야 되기 때문에 O(V^2)의 시간 복잡도를 갖는다..

Dijkstra algorithm Dijkstra Algorithm- 그래프 자료구조에서 노드 사이의 최단 경로를 찾는 알고리즘- 음의 가중치가 없는 그래프에서 한 노드에서의 모든 노드까지의 최단거리를 구하는 알고리즘- O(E*logV)의 시간복잡도를 가짐- 초창기에는 O(V^2)의 시간 복잡도를 가졌지만 우선순위 큐를 사용하는 방식이 생기면서 O(E*logV)의 시간복잡도로 더 개선된 알고리즘이 되었다. -> O(E*logV)의 시간 복잡도를 가지는 우선순위 큐를 사용하는 방식을 설명하려 한다. Dijkstra Algorithm Logic- 한 정점(노드)를 선택한다.- 아직 확인되지 않은 노드의 cost는 무한대로 초기화 시킨다.- cost가 적은 node들을 방문하며 모든 노드까지의 최단 경로를 찾..