플로이드 와샬
-
카카오 블라인드 2021) 합승 택시 요금알고리즘/프로그래머스 카카오 2021. 3. 7. 18:12
합승 택시 요금 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 플로이드-와샬을 이용해서 쉽게 풀 수 있었다. 주어진 각 구간마다의 요금을 플로이드-와샬을 통해, 연결된 구간을 이동하는데 최소 비용을 저장해주었다. 이후, 문제에서 요..
-
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년에 발표됨)과..