묻고 답해요
138만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
플로이드 워셜 관련 질문
플로이드 문제에서 가령 입력값이 아래와 같다고 할 때, 541 3 103 2 11 5 15 3 1 d[1][2] 의 값은 K = 3 일 때 d[1][2] = d[1][3] + d[3][2] = 11 그런데 d[1][3]은 이후에 K가 5일 때 연산을 통해d[1][3] = d[1][5] + d[5][3] = 2 근데 작아진 d[1][3]의 값이 반영되려면 K가 5일 때, d[1][5] + d[5][3] 연산을 한 '이후에' K가 3일 때d[1][2] =d[1][3] + d[3][2] 연산을 통해 d[1][2] 의 값이 바뀌어야 한다고 생각이 드는데 점점 증가해야 하는 K값이 값자기 작아질수는 없으니 그건 불가능합니다. d[1][2]의 값이 3이 되는데 필요한 어떤 연산을 제가 놓친건지 모르겠습니다...
-
미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
플로이드 워셜 알고리즘(1->5) 경우
i가 1, j가 5, k가 2인경우에 (1,5) 와 (1,2)+(2,5) 가 비교되는 경우가 생기는데 (2,5)의 값 같은경우 이전에 k=1일때 (2->1->5)의 값과는 계산해서 비교해 보았지만 반복문의 순서에 따라 k가 2,3,4,5 인 경우 즉 (2->3->5), (2->4->5) 이런경우들과 값을 비교해 보지 못하였다고 생각되는데 최솟값이라고 할 수 있는건가요?