TIL

오늘 한것 미래도시 - 플로이드 워셜 알고리즘 활용문제 학습 오늘 배운것 최단거리 문제에서 조건의 범위가 좁으면 플로이드 워셜을 고려할만 하다.

오늘 한것 플로이드 워셜 알고리즘 학습 오늘 배운것 플로이드 워셜 알고리즘은 모든 노드간의 최단경로를 구하는 알고리즘이다. 구현하는 코드 자체는 간단한데, 모든 노드를 순회하면서 현재 노드를 경유하는 경우의수를 모두 확인하면 되는것이다. 즉 모든 노드 순회(N) X 현재 노드를 경유하는 모든노드의 조합(N^2)이 된다. 모든 최단경로를 구하는 만큼 시간복잡도는 O(N^3)으로 느린 편이다. 정해진 노드(변하지 않는 시작점)에서의 최단경로를 구할때는 다익스트라 알고리즘을 사용하는것이 유리하다. 반드시 모든 노드간의 최단거리를 구해야만 하는 경우에는 플로이드 워셜 알고리즘을 사용한다.

오늘 한것 다익스트라 알고리즘 우선순위 큐 구현버전 학습 힙 자료구조 학습 오늘 배운것 힙 자료구조는 완전이진트리로 구현되어있으며, 루트의 값이 항상 자식보다 크거나 작은 일관된 규칙을 유지한다. 따라서 탐색, 저장 시 이진트리의 특징인 logN의 시간복잡도를 가지게 된다. 다익스트라 알고리즘에서는 가장 짧은 간선을 가진 노드를 계속해서 탐색해 나간다. 즉 최단거리 노드를 계속해서 탐색을 해야한다. 만약 탐색해야하는 자료구조가 리스트라면 별 수 없이 완전탐색을 해야하므로 시간복잡도는 O(N)이 된다. 그러나 힙을 탐색하는 경우 탐색에 O(logN)만 필요하게되므로 성능을 향상시킬 수 있다.

오늘 한것 다이나믹 프로그래밍 문제풀이 복습 오늘 배운것 점화식 세우기 연습