bsdlcksdn   10달 전

플로이드 와샬? 이라는 걸 처음접해봐서 잘 모릅니다;;;

다익스트라와 비슷한 느낌같아서 1238-파티 문제도 시간초과가 나더라구요;;(게시판에 글을 올렸으나 답이없네요;;)

제 생각대로 알고리즘 구현하여서 짜봤는데 시간초과가 나네요;

전자공학과 이다보니까 빅오 개념이나 시간복잡도를 잘 계산할줄 몰라요;;

어디서 시간초과가 가는건지 잘 모르겠습니다.

입력을 받고 n*n배열을 이중포문을 통해 재귀함수로 들어가게 되는데

그 밑에 이중포문 한 번 돌때마다 copy해놨던 배열을 다시 원본 배열에 입력시키는 과정에 의해 n*n*n*n이 됩니다.

혹시 이부분에서 시간초과가 나는걸까요??(n=100이라서 1억이라 시간초과가 안나지 않을까 햇는데요;;)

HJY   10달 전

o(n^4) 으로 짜셨다면, 시간초과가 날것 같습니다ㅜ

말씀하신 전쌍에 대한 최단경로를 구하는 플로이드워셜 알고리즘의 경우에는 시간복잡도가 O(n^3)입니다.
https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%E...
를 참고하시면 도움이 되실것 같습니다.!

다익스트라로 구현 하시는경우에도, 하나의 start 지점에서 나머지 노드들에 대해의 최단거리를 구하는데에 O(n^2)  혹은 자료구조에 따라 (nlog(n)) 이 소요됩니다.
따라서 다익스트라를 n번 돌리시면, o(n^3) 혹은 o(n^2 log(n)의  시간복잡도로 이문제를 해결하실수 있을것으로 보입니다.



댓글을 작성하려면 로그인해야 합니다.