[algorithm] Bellman-Ford

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 모든 노드에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다.시간복잡도 : $O(VE)$V : 정점의 개수E : 간선의 개수다익스트라 알고리즘은 이후에 방문할 음의 가중치 간선을 고려하지 않고 현재 노드에서 가장 최선

2020년 10월 4일
·
0개의 댓글

[algorithm] Floyd-Warshall

플로이드-워셜 알고리즘은 음의 가중치가 있고, 사이클이 있는 그래프에서 모든 노드에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다.시간복잡도 : $O(n^3)$graph TD A --> B B --> C

2020년 10월 3일
·
0개의 댓글

[algorithm] Dijkstra

Dijkstra 알고리즘은 음의 가중치가 없는 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다.우선순위 큐를 이용하여 구현할 경우 시간복잡도가 $O((V+E)logV)$가 된다.V : 정점의 개수E : 간선의 개수

2020년 10월 3일
·
0개의 댓글

[algorithm] 정렬

선택 정렬은 가장 작은 값을 찾아서 앞쪽의 값과 변경하면서 정렬하는 알고리즘이다.시간복잡도 : $O({n}^2)$삽입 정렬은 두번째 값부터 순회하면서 적절한 위치(이전 값보다 작아지는 곳)에 삽입하는 알고리즘이다.시간복잡도 : $O({n}^2)$버블 정렬은 인접한 값끼

2020년 10월 2일
·
0개의 댓글