hyunkookim 님의 블로그

797. All Paths From Source to Target 이 문제는 DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 시작 노드(0)에서 목표 노드(n−1)로 가는 모든 경로를 찾는 것입니다. 이 과정은 DFS(깊이 우선 탐색)를 이용하여 해결할 수 있습니다. 아래는 코드의 주요 흐름에 대한 한글 설명입니다.DFS 함수 정의:dfs 함수는 현재 노드(node)와 현재까지 탐색한 경로(path)를 인자로 받습니다.만약 현재 노드가 목표 노드(n−1)라면, 지금까지의 경로를 결과 리스트(result)에 추가합니다.재귀와 백트래킹:현재 노드의 모든 이웃 노드(neighbor)를 탐색합니다.이웃 노드를 경로에 추가한 뒤, 재귀적으로 dfs를 호출합니다.재귀 호출이 끝난 후에는 ..

215. Kth Largest Element in an Array Given an integer array nums and an integer k, return the kth largest element in the array.Note that it is the kth largest element in the sorted order, not the kth distinct element.Can you solve it without sorting? Example 1:Input: nums = [3,2,1,5,6,4], k = 2Output: 5Example 2:Input: nums = [3,2,3,1,2,4,5,5,6], k = 4Output: 4 Constraints:1 -104  정렬 하는 방법def fi..

class Solution: def findPeakElement(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l 162. Find Peak Element https://youtu.be/kMzJy9es7Hc?si=qJwIqyACFE9BAEzXclass Solution: def findPeakElement(self, nums: List[int]) -> int: l,r = 0, len(nums)-1 while l 시간 복잡도가 O (log n) 이므로, 이진 탐색으로 풀어야 함 ! 풀이1)class Solution: def findPeakElement(self, nums: List..

399. Evaluate Division visited 변수를 dfs 생성 할때마다 생성 Runtime: 0ms, Beats100.00%Memory: 16.70MB, Beats49.42%from collections import defaultdict, dequeclass Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # 1. 그래프 생성 adj = defaultdict(list) for (src, dst), val in zip(equations, values): adj[..

199. Binary Tree Right Side View # 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: # return root, null 을 반환하면 안되고, []을 반환해야함 return [] ..

236. Lowest Common Ancestor of a Binary Tree LCA(최저 공통 조상) 찾기노드 자신도 공통조상이 될수 있음재귀로..일단 루트가 none 이면 return 또는 return root루트가 p 또는 q 인지 체크해서 맞으면 루트 반환아니면, ..class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root: # 빈 노드면 return ## return root if root == p or root == q: return root # 좌측에..

11. Container With Most Water You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).Find two lines that together with the x-axis form a container, such that the container contains the most water.Return the maximum amount of water a container can store.Notice that you may not slant the containe..

392. Is Subsequence Given two strings s and t, return true if s is a subsequence of t, or false otherwise.A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not). Example 1:Input: s = "abc", ..

452. Minimum Number of Arrows to Burst Balloons There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.Arrows can be shot up directly vertic..

208. Implement Trie (Prefix Tree) A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.Implement the Trie class:Trie() Initializes the trie object.void insert(String word) Inserts the string word into the trie.boolean se..