Algorithm175 11657. 타임머신 (Swift, Python) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 문제이다. 1번에서 다른 모든 도시까지의 최단 경로를 구해주면 되는데 이때 걸리는 시간 C가 양수가 아닌 경우가 주어진다. 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하는 경우 대표적으로 다익스트라 알고리즘을 사용하면 되지만 다익스트라 알고리즘의 경우 간선.. 2021. 11. 14. [최단경로 알고리즘 - 3] 벨만 포드 알고리즘 * 벨만 포드 알고리즘이란? 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 벨만 포드 알고리즘의 특징은 다음과 같다. 1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 2. 음수 사이클의 존재 여부를 알 수 있다. 음수 사이클 안에서 무한루프를 도는 경우를 알 수 있는 방법은, 그래프 정점의 개수를 V라고 할 때 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1 번으로 제한하면 가능해진다. 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거쳐 가는 최대 간선 수는 V-1개이기 때문에 V번째 간선이 추가되는 순간 사이클이라고 판단할 수 있게 된다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다. 매번 모든 간선을 전부 확인하기.. 2021. 11. 14. 11404. 플로이드 (Swift, Python) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 적용하는 문제. 모든 도시에서 다른 모든 도시까지의 최단거리를 구해준다. 간단하게 플로이드 워셜 알고리즘을 적용하면 되는데 문제에서 주어진 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.'만 주의하면 된다. a에서 b로 가는 도시의 노선이 여러개 주어질 수 있는데 그 중 가장 적은 비용이 드는 노선을 배열에 설정해줘야 한다. 코드 [Swift] 1 .. 2021. 11. 12. [LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (swift, python) Find the City With the Smallest Number of Neighbors at a Threshold Distance - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 각 도시에서 distanceThreshold 이하의 거리를 갖고 있는 도시의 개수를 카운트 해야 한다. 즉, '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 해당한다. 그렇기 때문에 최단 경로 알고리즘에서 플로이드 워셜 알고리즘을 사용해서 풀 수.. 2021. 11. 12. [최단경로 알고리즘 - 2] 플로이드 워셜 알고리즘 * 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 알아볼 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점에서 다익스트라 알고리즘과 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜의 총 시간 복잡도는 O.. 2021. 11. 11. [LeetCode] 743. Network Delay Time (swift, python) Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 다익스트라 알고리즘을 활용해서 풀 수 있는 문제. 시작점 k에서 모든 노드까지의 최단거리를 구해준다. distance 배열에 k에서 각 노드 까지의 최단거리가 구해진다. 문제에서 모든 노드에 신호를 보내기까지 걸리는 시간을 구하라 했으므로 distance 배열에서 가장 큰 값(걸리는 시간이 가장 큰 경우)이 문제의 답이 된다. 만약 k에서 시작해서 도달할 수 없는 노드가 있.. 2021. 11. 3. 이전 1 ··· 23 24 25 26 27 28 29 30 다음
