hyunkookim 님의 블로그

211. Design Add and Search Words Data Structure https://youtu.be/BTf05gs_8iU?si=Oj37OnsdmiSq4Yfd class TrieNode(): def __init__(self): self.children = {} # a: TrieNode self.word = False # 현재 노드가 단어의 끝인지 표시class WordDictionary: def __init__(self): self.root = TrieNode() # Trie의 루트 노드 초기화 def addWord(self, word: str) -> None: cur = self.root # 루트 노드부터 시작 ..

127. Word Ladder 이 문제는 "단어 변환"과 관련된 그래프 탐색 문제입니다. 주어진 시작 단어(beginWord)에서 끝 단어(endWord)까지 최소 몇 번의 단어 변환으로 도달할 수 있는지를 찾는 것입니다. 단, 변환 규칙은 다음과 같습니다:문제 규칙단어 변환 조건:변환 시 한 번에 한 글자만 변경할 수 있습니다.예를 들어, hit에서 hot으로는 변환 가능하지만, hit에서 dot으로는 한 번에 변환할 수 없습니다.변환 과정 제약:변환된 중간 단어는 반드시 wordList에 포함되어야 합니다.beginWord는 wordList에 없어도 변환 가능합니다.목표:beginWord에서 시작하여 endWord로 변환하는 가장 짧은 경로의 길이를 반환합니다.변환이 불가능한 경우 0을 반환합니다.입..

909. Snakes and Ladders https://youtu.be/6lH4nO3JfLk?si=VJAa2R-huRKNzl6O 문제 설명 요약게임 보드 구조:n x n 크기의 정수 행렬 board가 있습니다.board는 Boustrophedon 스타일로 채워져 있습니다:숫자는 아래 왼쪽에서 시작하여 첫 줄은 왼쪽 → 오른쪽으로 채워지고,다음 줄은 오른쪽 → 왼쪽으로 채워지는 식으로 반복됩니다.각 칸은 1부터 n2까지의 숫자로 라벨링됩니다.초기 상태:게임은 1번 칸(왼쪽 아래)에서 시작합니다.이동 규칙:매 턴마다 주사위를 굴려 1에서 6 사이의 값을 얻습니다.현재 칸 curr에서 [curr + 1, min(curr + 6, n^2)] 범위 내의 칸 중 하나로 이동합니다.예: 현재 칸이 10이면, 다음 ..

149. Max Points on a Line https://youtu.be/Bb9lOXUOnFw?si=srijUp6iwLeL2_n5 class Solution: def maxPoints(self, points: List[List[int]]) -> int: # 1. for each pt determin if it lies on the logest line # 2. count all pts with same slop # 3. update result with max res = 1 # 최소 포인트 개수가 1개 이므로, 1개는 게런티 가능해서, for i in range(len(points)): p1 = points[i..

50. Pow(x, n) Time Limit Exceededclass Solution: def myPow(self, x: float, n: int) -> float: res = 1 if n>0: for i in range(1, n+1): res *= x elif n  이진 분할(분할 정복) 기법을 활용하여 효율적으로 해결할 수 있습니다. 이는 반드시 이진 트리를 명시적으로 사용하는 것은 아니지만, 개념적으로 재귀적으로 문제를 반으로 나누는 방식이 이진 트리의 구조와 유사합니다.  def myPow(x: float, n: int) -> float: # 음수 지수 처리 if n  이진 트리와의 ..

69. Sqrt(x) 통과는 하지만, 쫌 오래 걸림class Solution: def mySqrt(self, x: int) -> int: i = 0 while(i>=0): if (i*i == x): return i elif (i*i > x): break i+=1 return i-1 https://youtu.be/zdMhGxRWutQ?si=DRszQKJf3yNpiTyt 바이너리 써치로..class Solution: def mySqrt(self, x: int) -> int: # 바이너리 써치로. 이진 탐색 ..

295. Find Median from Data Stream https://youtu.be/itmhHWaHupI?si=QWJJw3c9WUZ0gmFN class MedianFinder: # 힙에서 데이터 추가/삭제는 O(log N) 이고, 검색은 O(1) 임 # small heap 은 max heap 으로, large heap 은 min heap 으로.. # max heap 을 pop 하면, # 가장 큰값이 추출되므로 이것을 large heap으로 바로 보낼 수 있음 # 우선 small heap 에 데이터 넣고 # 발란스가 small heap 이 더 크면, small heap 의 최대갑을 large heap 으로 넣고 # 여기서 발란스는 ..

373. Find K Pairs with Smallest Sums https://youtu.be/Youk8DDnLU8?si=dTtsC6RqlaGW-wWl class Solution: def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]: res = [] if not nums1 or not nums2 or not k: return res heap = [] visited = set() # 1번째 pair 추가: 정렬되어 있으므로, 둘다 첫번째, idx=0 이면, 합이 최소 # 힙에 (sum, i, j) 추가..

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

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