hyunkookim 님의 블로그

1700. Number of Students Unable to Eat Lunch https://youtu.be/d_cvtFwnOZg?si=KkHPkdE6CuKThQq4 class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) -> int: # 전체 학생 수 (Total number of students) res = len(students) # 학생들의 선호도를 카운트하기 위한 Counter 생성 # Create a Counter to count the preferences of students. # 예: students = [1, ..

684. Redundant Connection https://youtu.be/1lNK80tOTfc  https://youtu.be/FXWRE67PLL0?si=09q1EDMfBhbMNpJk class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # Union-Find 알고리즘으로 사이클을 형성하는 간선을 찾는 함수 # Use Union-Find algorithm to find the edge that creates a cycle. n = len(edges) # 간선의 개수 (Number of edges) # 부모 노드를 저장하는 배열 ..

323. Number of Connected Components in an Undirected Graph 내 풀이class Solution: def countComponents(self, n: int, edges: List[List[int]]) -> int: # 그래프를 인접 리스트로 표현 (Represent the graph as an adjacency list) hashMap = {i: [] for i in range(n)} # 각 노드 i를 키로, 빈 리스트를 값으로 초기화 (Initialize each node with an empty list) for n1, n2 in edges: # 간선 정보를 순회하며 그래프를 채움 (Iterate over ed..

142. Linked List Cycle II 이 문제는 Linked List Cycle Detection 문제 중 하나로,**Floyd's Cycle Detection Algorithm (Tortoise and Hare)**를 활용하여 해결할 수 있습니다.아래는 단계별 풀이 방법입니다.1. Floyd’s Cycle Detection Algorithm (토끼와 거북이)두 포인터(Tortoise와 Hare)를 사용하여 Linked List를 순회합니다.속도 차이를 이용해 두 포인터가 같은 노드에 도달하면 사이클이 있음을 확인할 수 있습니다.사이클이 발견되면, 사이클의 시작 노드를 찾는 추가 작업을 수행합니다.2. 단계별 풀이1단계: 사이클 존재 여부 확인slow 포인터는 한 번에 한 노드씩 이동합니다.fa..

997. Find the Town Judge class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: # 1. 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(1, n + 1)} # 신뢰 관계 for a, b in trust: adj[a].append(b) # a가 b를 신뢰 # 2. 판사 후보 선정 # 판사는 누구도 신뢰하지 않아야 하므로, 신뢰 관계가 없는 노드를 후보로 선정 candidates = [i for i in range(1, n + 1) if not adj[i]] if..

1971. Find if Path Exists in Graph class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: # 양방향 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(n)} for n1, n2 in edges: adj[n1].append(n2) adj[n2].append(n1) # 방문한 노드를 추적하기 위한 집합 visit = set() # DFS 함수 정의 def dfs(i): ..

261. Graph Valid Tree https://youtu.be/bXsUuownnoQ?si=hDkFB87rMA-fL6M4 class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: # 만약 노드의 개수가 0이라면, 빈 트리로 간주되므로 True 반환 # If there are no nodes (n == 0), it's considered a valid empty tree. if not n: return True """ 유효한 트리가 되기 위한 조건 (Valid Tree Conditions): 1. 노드 개수 - 1 == 간..

417. Pacific Atlantic Water Flow 이 문제는 두 개의 대양(태평양과 대서양) 모두로 물이 흐를 수 있는 위치를 찾는 것입니다. 각 셀의 물은 다음 조건을 만족할 때 이동합니다:인접한 셀의 높이가 현재 셀보다 작거나 같아야 합니다.물이 태평양과 대서양의 경계에서 시작하여 거꾸로 퍼져 나가야 효율적으로 풀 수 있습니다.문제를 해결하기 위한 접근 방식거꾸로 흐르는 관점(BFS/DFS):태평양과 대서양의 경계에서 각각 시작하여 물이 역으로 퍼져 나가는 방식으로 탐색합니다.각각의 대양에 도달할 수 있는 셀을 계산하고, 두 대양 모두에 도달 가능한 셀을 찾습니다.탐색 방향:네 방향(상, 하, 좌, 우)으로 이동하면서 물이 흐를 수 있는지 확인합니다.조건: height[다음 셀] >= hei..

286. Walls and Gates from collections import dequefrom typing import Listclass Solution: def wallsAndGates(self, rooms: List[List[int]]) -> None: """ Do not return anything, modify rooms in-place instead. """ """ 문제 설명: -1: 벽 또는 장애물로 이동 불가능한 위치를 나타냄 0: 게이트(문)가 있는 위치 INF (2147483647): 빈 공간으로, 게이트까지의 거리를 계산해야 함 목표: 각 빈 공간(21..

1091. Shortest Path in Binary Matrix 가장 짧은 경로 문제: BFS => 큐     cf) 목적지까지 갈수있는 경로 개수: DFS => 재귀 class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: N = len(grid) # n x n matrix if not grid: return -1 if grid[0][0] == 1 or grid[N-1][N-1] == 1: return -1 # shotedpath: using bfs, que def bfs(grid): q..