EI_HJ

https://programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으..

Floyd-Warshall(플로이드와샬 알고리즘)이란? - 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘. - 음수 가중치에 대한 처리가 어려운 다익스트라 알고리즘에 비해 플로이드 와샬 알고리즘은 사이클이 없는 경우 음수 가중치 처리가 가능 - for문(반복문)을 vertex(정점)만큼 3번 돌기 때문에 O(n3)의 시간 복잡도를 가진다. Floyd-Warshall process - 2차원 배열의 크기만큼 배열을 선언해준다. (각 정점에서 모든 정점을 가는 최소거리를 표현해줄 것이다.) - 연결돼있는 부분을 표기해준다. - 시작 정점에서 목표 정점까지 바로 가는 거리보다 또 다른 정점을 거쳐 지나가는 거리가 짧으면 업데이트를 해준다. - 플로이드 워샬 알고리즘에서는 1부터 시작해서 n까지 순차적..