hyunkookim 님의 블로그

1584. Min Cost to Connect All Points 1) 프림 알고리즘으로..import heapqclass Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: # points: [xi, yi] 형태의 2차원 좌표들이 주어짐 # 모든 점들을 연결하는 최소 비용을 구해야 하며, # 비용은 맨해튼 거리 |xi - xj| + |yi - yj| N = len(points) # 총 점의 개수 adj = {} # 인접 리스트 생성: 각 노드마다 [거리, 이웃노드] 목록 저장 for x in range(N): adj[x]..

Prim's AlgorithmSolved HardImplement Prim's minimum spanning tree algorithm.A Minimum Spanning Tree (MST) is a tree that spans all the vertices in a given weighted, undirected graph while minimizing the total edge weight and avoiding cycles. It connects all nodes with exactly ∣V∣−1∣V∣−1 edges, where VV is the set of vertices, and has the lowest possible sum of edge weights.Prim's algorithm is a ..

1514. Path with Maximum Probability 이 문제는 확률 기반 최단 경로 문제로,다익스트라(Dijkstra) 알고리즘을 확률 최대화 버전으로 변형해서 푸는 문제입니다.문장을 하나씩 해석하고 → 문제 핵심 → 해결 아이디어까지 차근히 설명드릴게요. 😊📖 한 문장씩 해석You are given an undirected weighted graph of n nodes (0-indexed),👉 0부터 시작하는 노드 번호를 가진 무방향 가중치 그래프가 주어집니다.represented by an edge list where edges[i] = [a, b]👉 간선 목록 edges[i] = [a, b]는 a와 b 노드를 연결하는 무방향 간선을 의미합니다.with a probability o..

778. Swim in Rising Water You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).👉 n x n 정수 행렬 grid가 주어지며, grid[i][j]는 (i, j) 지점의 **고도(elevation)**를 나타냅니다.The rain starts to fall.👉 비가 내리기 시작합니다.At time t, the depth of the water everywhere is t.👉 시간 t가 되면, 모든 지점의 물 깊이는 t입니다.You can swim from a square to another 4-directionally adjac..

743. Network Delay Time 이 문제는 그래프 문제로, **다익스트라 알고리즘(Dijkstra's Algorithm)**을 사용해서 해결할 수 있는 전형적인 단일 출발점 최단 경로 문제입니다. 아래에 차근차근 설명해드릴게요.✅ 문제 요약노드가 1부터 n까지 있고,times = [[u, v, w], ...] 형식으로 **방향성(edge)**과 **가중치(weight)**가 주어짐.u에서 v로 가는 데 w 시간이 걸린다는 뜻.시작 노드 k에서 신호를 보낼 때, 모든 노드가 신호를 받는 데 걸리는 시간 중 가장 오래 걸리는 시간을 구해야 함.모든 노드가 도달 불가능하다면 -1을 리턴함. Return the minimum time it takes for all the n nodes to recei..

47. Permutations II "중복 숫자가 포함된 리스트에서 모든 유일한 순열을 반환하라"는 문제입니다.✅ 핵심 포인트 요약nums에 중복 원소가 존재할 수 있음따라서 단순한 백트래킹으로 모든 순열을 생성하면 중복된 결과가 포함됨→ 정렬 + 백트래킹 중 중복 조건 체크로 중복 제거 필요✅ 최적 풀이 (정렬 + used[] + 가지치기)from typing import Listclass Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: # 결과를 저장할 리스트 res = [] # 중복 숫자를 인접하게 만들어 중복 제거가 쉽게 되도록 정렬 nums.sort() ..

✅ 순열 (Permutation) 요약 정리:정의:주어진 원소들을 모두 사용하여, 순서를 고려해 나열하는 것.예시:{1, 2, 3}의 순열 →[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]총 3! = 6가지순열 vs 조합  구분 순열 (Permutation) 조합 (Combination) 순서중요함중요하지 않음원소 사용모두 사용함일부만 사용할 수도 있음예시(1,2,3), (1,3,2) 등{1,2}, {2,3} 등💡 수학 공식:n개의 서로 다른 원소를 모두 사용한 순열의 개수:n! (팩토리얼)예: 3! = 3 × 2 × 1 = 6✅ 재귀 방식 permutationsRecursive(nums)# 시간 복잡도: O(n^2 * n!)def permutation..

480. Sliding Window Median heapq을 사용해 Two Heaps 방식으로 구현한 것입니다.앞서 봤던 방식과 비슷하지만,좀 더 간결하게 balance 변수로 크기 조정을 처리한 형태입니다. import heapqfrom collections import defaultdictfrom typing import Listclass Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: small, large = [], [] # small: 최대 힙 (음수 저장), large: 최소 힙 d = defaultdict(int) # 삭제 예약 딕셔..

145. Binary Tree Postorder Traversal 재귀 방법# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 후위 순회: 왼쪽 -> 오른쪽 -> 자신 if not root: return [] # 트리가 비어..

144. Binary Tree Preorder Traversal  재귀 방식 # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 전위 순회(preorder traversal): 자신 -> 왼쪽 -> 오른쪽 res = [] def dfs..