플로이드2 [Floyd] 플로이드 알고리즘 목차플로이드 설명플로이드 알고리즘 과정플로이드 알고리즘 시간 복잡도백준 11404 플로이드 골드4백준 11780 플로이드2 골드2참고 자료플로이드 설명Folyd(플로이드) 알고리즘은 그래프 최단 경로를 찾는 알고리즘 중 하나이다.정점1 → 정점3 : 최단경로는 1이다.정점3 → 정점5 : 최단경로는 3 → 4 + 4 → 5 = 3 + 6 = 9 이다.플로이드 알고리즘 = 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘현재 그래프는 무방향(양방향) 그래프 이지만 그래프가 방향 그래프이건, 무방향 그래프이건 상관이 없다.간선의 값이 음수여도 잘 동작하지만, 음수인 사이클이 있으면 문제가 생긴다.하지만 애초에 간선의 값이 음수인 상황이 일반적이지는 않다.플로이드 알고리즘의 구현 난이도는 MST에 비해 비교적.. 2024. 5. 15. Java 프로그래머스 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분류 : 코딩테스트 연습 > Summer/Winter Coding(~2018) > 배달 난이도 : 2 문제 풀이1 (정답 코드) 다익스트라를 사용해서 풀었다. 근데 문제를 풀고 생각해 보니 한 번만 다익스트라를 돌려도 1에서 각 마을로 가는 최단거리는 모두 구했으니 메서드로 마을마다 매번 구할 필요가 없구나를 깨달았다. (문제 풀이2에 적용) import java.util.*; class S.. 2024. 2. 29. 이전 1 다음