플로이드 워셜
-
BOJ) 플로이드 (11404 번)알고리즘/백준 2021. 2. 12. 16:00
플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 도시의 쌍 (A, B)에 대해서 도시 A -> 도시 B로 가는데 필요한 비용의 최솟값을 구하는 문제다. 사실, 최단거리를 보면 다익스트라를 가장 먼저 떠올렸을 것이다. 플로이드-워셜에 분류되어 있어서 플로이드-워셜 방법으로 접근을 했다. 근데, 다시 생각해보면, 모든 경로를 구해야하기 때문에, 모든 도시의 쌍 (A,B)의 거리를 다익스트라로 구한다고하면, 시간이 더욱 오래 걸릴 것 같다. 모든 도시의 쌍의 최단 거리 정보를 저장해두는 플로이드 워셜이..
-
BOJ) 키 순서 (2458 번)알고리즘/백준 2021. 2. 10. 16:39
키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net Floyd Warshall 아래는 위키에 설명된 내용을 가져왔다. 플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다.[3] 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘[4]과, 스티븐 워셜이 1962년에 발표한 알고리즘[5]과 그래프의 추이적 폐포를 찾는다는 점,[6]그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과..