hyunkookim 님의 블로그

502. IPO 이 문제는 Greedy + Heap을 활용해서 해결할 수 있는 IPO 자본 최대화 문제입니다.주어진 프로젝트 중 최대 k개를 골라 이익을 최대화하는 것이 목표입니다.✅ 문제 요약각 프로젝트는 다음 정보를 가짐:profits[i]: 이익capital[i]: 최소 시작 자본시작 자본: w프로젝트를 최대 k개까지 선택할 수 있음조건:현재 자본 w 이상을 요구하는 프로젝트만 수행 가능프로젝트를 수행하면 그 이익만큼 자본 증가✅ 핵심 아이디어🎯 항상 지금 당장 수행 가능한 프로젝트 중에서 이익이 가장 큰 것을 선택✔ 자료구조 선택모든 프로젝트를 (capital, profit) 형태로 정렬하여 준비매 순간, 현재 자본 w로 수행 가능한 프로젝트를 **최대 힙(max heap)**에 저장힙에서 가장..

74. Search a 2D Matrix class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS = len(matrix) COLS = len(matrix[0]) l, r = 0, COLS*ROWS - 1 while l target: r = mid-1 else: return True return False https://youtu.be/Ber2pi2C0j0 class Solution: def searchMatrix(self, matrix: List[List..

918. Maximum Sum Circular Subarray 내 코드class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: maxSum = nums[0] curSum = 0 for n in range(len(nums)*2): if curSum  이 코드는 틀렸음. %  모듈러 연산으로 회전 행렬을 반영하고 있으나.행렬 길이를 고려하고 있지 않음. class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: maxSum = nums[0] curSum =..

53. Maximum Subarray class Solution: def maxSubArray(self, nums: List[int]) -> int: l, r = 0, len(nums)-1 # window = l-r # l는 1개씩 증가하는데, # l부터 len(nums) 까지, max_sum 계속 구함 max_sum = -float("inf") for l in range(len(nums)): # if nums[l]  Time Limit Exceeded https://youtu.be/5WZl3MMT0Eg?si=F16OBsmPYHPefkwv class Solution: def maxSubArray(s..

210. Course Schedule II Hint 1 This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.  Hint 2 Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. Hint 3 Topological sort could also be done vi..

133. Clone Graph 이 문제는 연결된 무방향 그래프를 깊은 복사(deep copy)하라는 것입니다. 조금 더 쉽게 설명하자면, 그래프 전체를 복제하라는 것입니다. 그래프는 노드들로 이루어져 있고, 각 노드는 값(val)과 이웃 노드 목록(neighbors)을 가지고 있어요.핵심 포인트입력으로 주어진 그래프는 Node로 표현된 연결 그래프입니다.예를 들어, 노드 1은 Node(1)이고, 이웃 노드가 [2, 4]라면 Node(1).neighbors = [Node(2), Node(4)]와 같은 식으로 표현됩니다.이웃 노드가 연결된 그래프를 복사할 때, 모든 노드와 이웃 정보를 새로운 그래프로 깊은 복사를 해야 합니다.단순히 복사하는 것이 아니라, 새로운 메모리에 새로운 노드들을 만들어야 합니다.그래..

200. Number of Islands https://youtu.be/pV2kpPD66nE?si=lYen92FEUHgGfFzQ class Solution: def numIslands(self, grid: List[List[str]]) -> int: # grid가 비어있으면 0을 반환 (예외 처리) # If the grid is empty, return 0 (edge case handling) if not grid: return 0 # grid의 행(Row) 수와 열(Col) 수를 변수에 저장 # Store the number of rows (ROWS) and columns (COLS) in variables ..

105. Construct Binary Tree from Preorder and Inorder Traversal https://youtu.be/ihj4IQGZ2zc?si=xp7MO4VGo3NIKjnW class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # 문제 접근법: # 1. Preorder 배열의 첫 번째 값은 항상 현재 서브트리의 루트 노드 값입니다. # 1. The first value in the preorder array is always the root node of the current subtree. # 2...

146. LRU Cache https://youtu.be/7ABFKPK2hD4?si=R9ZwBAdBVxHzBRga # Node 추가 class Node: def __init__(self, key, val): self.key, self.val = key, val self.prev = self.next = Noneclass LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} # map key to node # left=LRU, right=most recent self.left, self.right = Node(0, 0), ..

21. Merge Two Sorted Lists # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() res = dummy while list1 and list2: v1 = list1...