목록2024/02/26 (5)
미소를뿌리는감자의 코딩
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 접근 방법 Floyd - Warshall 로 이 문제를 접근하였다. 각각의 노드에 대해서, a 에서 b로 가는 최솟값이 나타날 수 있다는 점에서 floyd - warshall 이 장점이 있는 것 같다. 처음에 Dijkstra로 문제를 풀었으나, 해당 문제에서는 시간 초과가 나서 풀 수 없었다. 일반적인 floyd - warshall 코드에, for a in ..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 접근 방법 전형적인 dijkstra 문제였다. 코드에 주석을 달아서 더 설명해 보도록 하겠다. 2. 코드 import heapq INF = int(1e9) def findCheapestPrice(n, src, nodes): # edge들을 저장한 nodes를 넘겨 받았다. dist = [INF] * (n + 1) # dist라는 list에 각각의 노드에 ..
https://leetcode.com/problems/cheapest-flights-within-k-stops/description/ Cheapest Flights Within K Stops - LeetCode Can you solve this real interview question? Cheapest Flights Within K Stops - There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to leetcode.com 1. 접근 방법 노..
https://leetcode.com/problems/network-delay-time/description/ Network Delay Time - LeetCode Can you solve this real interview question? Network Delay Time - You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the tar leetcode.com 1. 접근 방법 이번 문제는 Dijkstra 문제로, Dijkst..