그래프에서 최단 경로를 찾을 때, 플로이드 알고리즘을 이용하는 경우와 다익스트라 알고리즘을 이용하는 경우가 있다. 어떻게 다른가?
상위 100% ~ 상위 40% : ....플로이드가 뭐에요?
상위 39% ~ 상위 11% : 둘다 최단경로 찾는거 아닌가요? 다만 플로이드보다 다익스트라의 시간복잡도가 더 작으니까 다익스트라가 더 빠른 알고리즘?
상위 10%~ : 플로이드는 임의의 정점 A에서 B로 가는 모든 최단 경로를 찾을 때 사용하는 알고리즘이며, 다익스트라 알고리즘은 특정한 시작점에서 다른 정점으로 가는 최단경로를 찾을 때 사용하는 알고리즘입니다. 따라서 근본적으로 한 정점에서 다른 정점으로의 최단경로를 찾는 시간복잡도는 같으며, 다익스트라 알고리즘을 모든 정점에 대해 1번씩 돌릴 경우 플로이드 알고리즘과 동일한 결과가 나오게 됩니다.
너의 위치는?
cyclic directional graph 의 topological ordering 의 방법은?
지금 물어보면 2학년들은 모두 상위 10%가 된다. 시험에 나오니 외어야지
mozzart // indegree를 주면 되겠죠 앙기모띠
ㅋㅋㅋㅋㅋ 귀여워.
오일러 투어의 다른말이지 뭐.
통신에서 쓰는 알고리즘 아닌가요. 흠냥 오히려 알고리즘이낭 통신배우는 현역인 3학년때 잘알듯요
뭐에요->뭐예요 (받침 있으면 이에요 없으면 예요 이로 끝나면 받침 없으므로 예요 아니에요는 예외 인명엔 예요(예 : 길동이예요) 성까지 쓰면 이에요(예 : 홍길동이에요))[리듬 맞춤법 봇♬]
플로이드는 다이나믹 다익스트라는 그리디
sparse graph 에서는 dijkstra가 all pair shortest path 찾는데 플로이드 보다 더 빠른데염
저걸로 상위 10프로는 무리지 싶다...
mozzart/ directed acyclic graph 잘못 말한거 아니신지..
그건 넘 쉽잖아. 걍 topological sort 지.
DAG 이야기 하는거 아님유~
어떻게 저걸로 상위 10%?