hyunkookim 님의 블로그

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

height 는 자식이 없는 노드가 1이고Depth 는 부모 root 노드가 1로 시작 DFS 검색 방법: 깊이 우선 탐색 (Depth-First Search, DFS)깊이 우선 탐색(DFS)은 코딩 인터뷰에서 가장 자주 등장하는 알고리즘 중 하나입니다. 주로 트리나 그래프를 탐색할 때 사용됩니다. 이 강의에서는 트리 탐색에 초점을 맞춰 설명하겠습니다. 트리 전체를 탐색하려면 모든 노드를 방문해야 합니다. 이때 사용할 수 있는 방법 중 하나가 깊이 우선 탐색입니다.기본 아이디어는 어떤 방향(예: 왼쪽) 을 먼저 선택해서, 해당 방향으로 갈 수 있을 때까지 계속 내려가는 것입니다. 즉, 왼쪽 자식 노드를 따라 계속 내려가다가 더 이상 노드가 없으면(null에 도달하면), 부모 노드로 되돌아가서 이번엔 오른..

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

695. Max Area of Island BFS로 풀기from typing import Listfrom collections import dequeclass Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: # 섬 개수 및 최대 면적을 계산하는 함수 # Count the number of islands and calculate the maximum area # 네 방향 이동: 상, 하, 좌, 우 # Directions for movement: up, down, left, right directions = [[1, 0], [-1, 0], [0, 1], [..

297. Serialize and Deserialize Binary Tree # bfs(큐) 또는 dfs(preorder 순회: 나-좌-우) # null 대신 N 으로 DFS: preorder 가 더 쉽게 구현 가능 https://youtu.be/u4JAi2JJhI8 # Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Codec: def serialize(self, root): """Encodes a tree to a single stri..

110. Balanced Binary Tree # 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 isBalanced(self, root: Optional[TreeNode]) -> bool: # 높이 균형 이진 트리는 각 노드의 두 서브 트리의 깊이가 1 이상 차이가 나지 않는 이진 트리입니다. # height-balanced tree: 높이 균형 이진 트리는, ..

543. Diameter of Binary Tree 트리의 Diameter 즉, 지름을 구하려면,어떤 노드를 기준으로, 좌측 최장 길이+오른쪽 최장 길이..꼭. 이 노드가 root 가 아닐 수도 있음: The path does not necessarily have to pass through the root.위 의 경우, 노드 3을 기준으로, 왼쪽 2, 오른쪽 2... 그래서 diameter 는 2+2=4 임 따라서,전역 변수 max_length 만들고, 모든 노드를 탐색하면서, 왼쪽+오른쪽 길이, 즉, max_lengh를 계속 업데이트 해야함. 모든 노드 탐색시, dfs,,,로 # Definition for a binary tree node.# class TreeNode:# def __init_..

94. Binary Tree Inorder 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # inorder: dfs 에서,.. 왼쪽, 현재, 오른쪽 순회 # dfs 니깐, stack 이나 재귀로 if not root:..

Inorder Traversal 순회왼쪽 -> 현재 -> 오른쪽https://youtu.be/hUaKh73y9lc Preorder Traversal 순회현재 -> 왼쪽 -> 오른쪽  https://youtu.be/KReQI3Muebg Postorder Traversal 순회왼쪽 -> 오른쪽 -> 현재   https://youtu.be/bJoMy7V0jQw

111. Minimum Depth of Binary Tree if not root: 루트 비어 있는 경우    return 0 : 깊이는 0 root 부터, 깊이는 1 자식이 둘다 없으면 leaf 노드 임if not node.left and not node.right:   return 깊이 최소 값 업데이트 # 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 minDepth(self, r..