이코테 정확한 순위 Python더보기❍ 문제선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다.학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다.1번 학생의 성적 3번 학생의 성적 4번 학생의 성적 4번 학생의 성적 5번 학생의 성적 5번 학생의 성적 A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 위의 성적 결과를 다음 그림처럼 표현할 수 있습니다.이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 ..

백준 플로이드 파이썬 11404https://www.acmicpc.net/problem/11404 더보기❍ 문제n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.❍ 입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 ..

들어가며 본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다. 📌 플로이드 워셜 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다. 기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다. 모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다. ☑️ 시간 복잡도 모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N..