Scribbling

src로부터 특정 dst까지의 최단 거리를 묻는 문제로, 다익스트라 알고리즘을 먼저 떠올릴 수 있다. 기본적인 형태의 다익스트라 알고리즘은, priority queue에 "최단 거리가 갱신되는 경우"를 추가한다. 하지만 이 문제는 "이동 횟수 제한"이 있으므로, 이를 수정해야한다. 즉, priority queue에 "최단 거리가 갱신되는 경우"를 추가하는 것이 아니라, "추가적으로 이동 가능한 경우"를 모두 추가할 필요가 있다. 이를 코드로 구현하면 아래와 같다. import heapq class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: INF = int..

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: char_set = set() l = 0 max_len = 0 for r in range(len(s)): if s[r] in char_set: while s[r] in char_set: char_set.remove(s[l]) l += 1 char_set.add(s[r]) max_len = max(max_len, r - l + 1) return max_len

class Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: INF = int(1e9) distance = [[INF] * (n) for _ in range(n)] for i in range(n): distance[i][i] = 0 for edge in edges: u = edge[0] v = edge[1] w = edge[2] distance[u][v] = w distance[v][u] = w for k in range(n): for a in range(n): for b in range(n): distance[a][b] = min(distance[a][b], distance[a][k..

다익스트라 알고리즘을 활용하여 푼다. import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: INF = int(1e9) graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for time in times: u = time[0] v = time[1] w = time[2] graph[u].append((w, v)) self.dijkstra(graph, distance, k) max_dist = 0 for i in range(1, n+1): max_dist = max(max_dist, distance[i]) if max_dist ..

1. 노가다성 답안 class Solution: def addTwoNumbers(self, l1, l2, up=0): if l1 != None and l2 != None: val1 = l1.val val2 = l2.val val = (val1 + val2 + up) % 10 up = (val1 + val2 + up) // 10 ret_node = ListNode(val=val) ret_node.next = self.addTwoNumbers(l1.next, l2.next, up=up) elif l1 == None and l2 != None: val2 = l2.val val = (val2 + up) % 10 up = (val2 + up) // 10 ret_node = ListNode(val=val) ret_..