Scribbling

class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: def calc_Dist(p1, p2): d1 = abs(p1[0] - p2[0]) d2 = abs(p1[1] - p2[1]) return d1 + d2 def find_parent(parent, a): if parent[a] == a: return a parent[a] = find_parent(parent, parent[a]) return parent[a] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: ..

1. 신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다. 2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리 3. Kruskal Algorithm: 최소 신장 트리를 찾는 알고리즘 - O(vlogv) - Greedy하게 최소 비용 edge부터 차례로 연결한다. - 연결하고자 하는 node가 서로소였다면, union을 진행 - 연결하고자 하는 node가 cycle을만든다면, pass def find_parent(parent, x): if parent[x] == x: return x parent[x] = find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_p..

Dynamic Programming을 이용한 방법: X + + X 는 Palindrome Substring이다는 특성을 이용한다. 위를 bottom-up으로 구현하려면, 문자열의 길이가 커지는 순(1, 2, 3, ....) 으로 DP를 연산하면 된다. class Solution: def longestPalindrome(self, s: str) -> str: ret = "" is_Palindrome = [[False] * len(s) for _ in range(len(s))] for i in range(len(s)): is_Palindrome[i][i] = True ret = s[i:i+1] for i in range(len(s)-1): if s[i] == s[i+1]: is_Palindrome[i][i+..

1. 무향 그래프 내 Cycle 판별 - 서로소 집합 알고리즘을 사용한다. - 모든 edge에 대해 두 node의 부모가 같다면, cycle이 존재. 두 node의 부모가 다르다면, union 진행. v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a]..

v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: pa..

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

Set 자료형: 중복을 제거해준다. mySet = set([1, 2, 3]) 1) 데이터 추가 mySet.add(3) mySet.update([4, 5, 6]) 2) 데이터 삭제 mySet.remove(3): set에 3이 없으면 error mySet.discard(3): set에 3이 없어도 no error 3) Set에 데이터 추가/삭제는 O(1)

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..

최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq = [] heapq.heappush(pq, (0, start)) distance[start] = 0 while pq: dist_u, u = heapq.heappop(pq) # node u가 이미 처리된 경우 if distance[u] dist_uv + dist_u: distance[v] = dist_uv + dist_u heapq.heappush(pq, (..