hyunkookim 님의 블로그

1203. Sort Items by Groups Respecting 🔸 문제 설명There are n items each belonging to zero or one of m groups→ n개의 아이템이 있으며, 각 아이템은 m개의 그룹 중 하나에 속하거나, 어떤 그룹에도 속하지 않을 수 있습니다.where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group.→ group[i]는 i번째 아이템이 속한 그룹 번호이며, 그룹이 없는 경우 -1입니다.The items and the groups are zero indexed.→ 아이템과 그룹 번호는 모두 0번부터 ..

1462. Course Schedule IV class Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: # numCourses: 전체 수업 개수 (0부터 numCourses-1까지 번호가 매겨짐) # prerequisites[i] = [a, b]: 수업 a를 먼저 들어야 b를 들을 수 있음 (a → b) # queries[j] = [u, v]: u가 v의 직접 또는 간접 선행 과목인지 확인해야 함 # 1. 인접 리스트 (adjacency list)와 reachable ..

1) DFS 기반 위상 정렬# 주어진 방향성 있는 비순환 그래프(DAG)에서# 올바른 위상 정렬 순서를 반환하는 함수def topologicalSort(edges, n): # 1. 인접 리스트(adj)를 만들어서 그래프 구성 adj = {} for i in range(1, n + 1): adj[i] = [] # 각 노드를 key로 하여 빈 리스트 초기화 # 주어진 간선을 이용해 방향 그래프 구성 (src → dst) for src, dst in edges: adj[src].append(dst) # 2. 위상 정렬 결과를 담을 리스트 topSort = [] # 방문한 노드를 기록할 집합 visit = set() # 3. 모든 ..

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1,👉 가중치가 있는 무방향 연결 그래프가 주어지며, 이 그래프는 0부터 n - 1까지 번호가 매겨진 정점들을 포함합니다. and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi.👉 edges[i] = [ai, bi, weighti] 형식의 배열이 주어지고, 이는 정점..

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