목록Floyd-Warshall (2)
체뚱로그
풀이 시간: 2:15:06 시간 복잡도: O(n^3 + n^2) = O(n^3) // floyd_warshall()의 3중 for문 + main()의 2중 for문 공간 복잡도: O(n^2 + n) = O(n^2) // dist 공간 복잡도 O(n^2) + item 공간 복잡도 O(n) 참고 자료: https://velog.io/@yyj8771/Python-백준-14938번-서강그라운드 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못..
풀이 시간: 30:46 시간 복잡도: O(N+M+N^3) = O(N^3) // floyd_warshall()의 O(N^3) 공간 복잡도: O(N^2) // party_hall의 공간 복잡도 참고 자료: https://chanhuiseok.github.io/posts/algo-50/ 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 문제 파티를 좋아하는 민호는 끝없이 파티가 열리는 놀이동산 "민호월드"를 세웠다. 처음에는 한개의 파티장만을 가지고 있는 작은 놀이동산이었지만, 사람들의 점점 많이 찾아와 파티장을 증축했고 현재는 N개의 파티장을 가진 큰 놀이동산이 되었다. 민호는 파티장을 증축할때마다 편의를 위해 새로운 파..