hyunkookim 님의 블로그

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

1. Two Sum 최초 내 코드class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: l, r = 0, len(nums)-1 for l in range(len(nums)-1): for r in range(l+1, len(nums)): if nums[l]+nums[r] == target: return [l, r]  풀리긴 하지만, 아~ 주 비효율적임 https://youtu.be/KLlXCFG5TnA?si=hamrAV8oUfPTDA7b https://youtu.be/zH7F-qnTi74?si=lBLzCWaIWbKt..

17. Letter Combinations of a Phone Number GPT: 백트레킹class Solution: def letterCombinations(self, digits: str) -> List[str]: # 1. 숫자와 문자 매핑 정의 phone_map = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } # 2. 결과 리스트 초기화 res = [] # 3. 입력이 빈 문자열인 경우 빈 리스트 반환 i..

104. Maximum Depth of Binary Tree https://youtu.be/meKRO8w6KT8?si=dDC-xWB8fOBdng6_  1. 스텍을 이용: 깊이 우선 탐색 할때 주로 스텍을 사용스텍에, [(노드값, 깊이), ...] 이런식으로 추가스텍 팝 하고.. 그 자식노드를 스텍에 추가.. 하는 식으로..time: O(n)space: O(n) ```# 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 = right```cla..

72. Edit Distance https://youtu.be/XYi2-LPrwm4?si=8R5kcaUc9tWO8sSQ     초기값 세팅 설명초기 설정의 의미첫 번째 행과 열은 문자열이 비어 있을 때 작업의 기준점을 제공합니다.이후, 이 값을 기반으로 나머지 테이블 값을 채우며 두 문자열의 변환 비용을 계산합니다.이후 과정결론DP 테이블의 최종 값은 문자열을 변환하는 모든 가능한 경로를 고려해 최적의 변환 비용을 계산한 결과입니다. 이를 통해 삽입, 삭제, 교체 작업을 효율적으로 비교할 수 있습니다. Codeclass Solution: def minDistance(self, word1: str, word2: str) -> int: # DP 테이블 생성 # cache[i][..

문제198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.Given an integer array nums representing ..