hyunkookim 님의 블로그

1046. Last Stone Weight https://youtu.be/B-QCq79-Vfw?si=3xrwdkwlsVfUMrM8 class Solution: def lastStoneWeight(self, stones: List[int]) -> int: # 기본적으로 minHeap 이니깐, -1 곱하면 maxheap stones = [-s for s in stones] heapq.heapify(stones) print(stones) while len(stones) > 1: high_1st = heapq.heappop(stones) high_2nd = heapq.heappop(stones) ..

703. Kth Largest Element in a Stream https://youtu.be/hOjcdrqMoQ8?si=j-8DMVDjR9t8bNx_ class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.minHeap = nums heapq.heapify(self.minHeap) # 최소 힙의 크기를 k 개로 유지하기 위한 로직 while len(self.minHeap) > k: # nums 리스트의 길이가 k보다 큰 경우, # 가장 작은 값을 하나씩 제거하여 힙의 크기를 k로 줄임 he..

51. N-Queens https://youtu.be/Ph95IHmRp5M?si=nFzhZlWopNf9D4FI class Solution: def solveNQueens(self, n: int) -> List[List[str]]: """ - negDiag: ↖ ↘ 대각선 방향을 추적 (row - col = 일정한 값) - posDiag: ↗ ↙ 대각선 방향을 추적 (row + col = 일정한 값) - col: 퀸이 이미 배치된 열(column)을 추적 - 매 줄마다 퀸 하나씩 배치 가능 (한 행에 하나의 퀸만 존재) """ # 퀸이 배치된 열(colum..

131. Palindrome Partitioning https://youtu.be/3jvWodd7ht0?si=paC9K4J8hqA0IgZJ class Solution: def partition(self, s: str) -> List[List[str]]: # palindrome: 앞으로 읽으나 뒤로 읽으나 같은 문자열을 의미 res = [] # 모든 가능한 회문 분할 결과를 저장할 리스트 # 주어진 문자열이 palindrome인지 확인하는 함수 def isPalidrome(substring): # 문자열을 뒤집어서 비교하여 palindrome 여부 반환 return substring == substring[::..

90. Subsets II https://youtu.be/Vn2v6ajA7U0?si=w1awdAmx7zve9Tqv class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: # Sort the input list to group duplicates together # 입력 리스트를 정렬하여 중복된 숫자를 연속적으로 배치 nums.sort() # List to store all unique subsets # 모든 고유한 부분집합을 저장할 리스트 res = [] # Backtracking function # 백트래킹 함수 정..

40. Combination Sum II https://youtu.be/rSA3t6BDDwg?si=w-QEPd8Mv2Krb5C- class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: # Sort the candidates to facilitate duplicate removal # 후보 숫자를 정렬하여 중복된 숫자를 연속적으로 배치 candidates.sort() # To store the final combinations # 최종 결과를 저장할 리스트 res = [] ..

78. Subsets https://youtu.be/REOH22Xwdkk?si=J1EDs8ppnu7DJndK class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # subset 만들기 res = [] subset = [] def dfs(idx): if idx >= len(nums): print(idx, subset) res.append(subset.copy()) return # decision to include nums[idx] sub..

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

235. Lowest Common Ancestor of a Binary Search Tree https://youtu.be/gs2LMfuOR9k?si=KNjrz6AwcGwSPR0P # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # 공통 부모 찾기 # p..

572. Subtree of Another 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: def sameTree(n1, n2): if not n1 and not n2: # 둘다 없으면 ..