hyunkookim 님의 블로그

983. Minimum Cost For Tickets https://youtu.be/4pY1bsBpIY4?si=PbuLW3CZC5vqdJDg class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: # ✅ dp[i]는 i번째 여행일(day[i])부터 시작할 때 필요한 최소 비용을 저장 dp = {} # dfs(i): days[i]일부터 여행을 시작할 때 필요한 최소 비용을 반환 def dfs(i): # 종료 조건: 모든 여행일을 다 처리한 경우 → 추가 비용 없음 if i == len(days): ..

518. Coin Change II https://hyunkookim.tistory.com/279 Knapsack 문제(배낭 문제) : DP 최적화**Knapsack 문제(배낭 문제)**는 조합 최적화 문제로, 주어진 조건 하에서 최대 또는 최적의 결과를 찾는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming)이나 탐욕법(Greedy Algorithm)을 활용하여 풀hyunkookim.tistory.com Knapsack 문제와 동전 문제의 유사점Knapsack 문제와 동전 문제는 모두 조합 최적화 문제이며, 동적 계획법(DP)을 사용해 해결합니다.Knapsack 문제:최적의 가치를 찾는 것이 목표.각 물건의 가치와 무게가 있음.동전 문제:주어진 금액을 구성하는 조합의 수를 찾는 것..

115. Distinct Subsequences 두 문자열 s, t가 주어질 때, s로부터 t를 만들 수 있는 서로 다른 subsequence의 개수를 구하세요.subsequence: 문자의 순서는 유지하면서, 일부 문자를 생략한 것각 문자는 한 번만 사용 가능📌 예시 1Input: s = "rabbbit", t = "rabbit"  Output: 3s에서 'b'가 3번 등장하기 때문에, 각각을 생략하는 방식으로 3가지 방법이 존재📌 예시 2Input: s = "babgbag", t = "bag"  Output: 5다양한 'b', 'a', 'g' 조합이 존재해서 총 5가지 방법으로 만들 수 있음🔧 핵심 개념: dp[i][j]의 의미표현의미dp[i][j]s[0:i]로 t[0:j]를 만들 수 있는 su..

97. Interleaving String https://youtu.be/3Rw3p9LrgvE?si=Bs1PKA3LI4l3H4my class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: # 길이 조건 확인 if len(s1) + len(s2) != len(s3): return False dp = {} def dfs(i, j): # 종료 조건: s1과 s2를 모두 사용했을 때 if i == len(s1) and j == len(s2): return True # 이미 계산..

63. Unique Paths II  https://youtu.be/d3UOz7zdE4I?si=HXkXE8KW1a0v6Ed5 # Time: O(N*M), Space: O(N*M)from typing import Listclass Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: """ # Time: O(N*M), Space: O(N*M) """ # 격자의 행(M)과 열(N) 개수를 계산 M, N = len(obstacleGrid), len(obstacleGrid[0]) # 출발점이 장애물인 경우, 즉시 0 반환 if ..

23. Merge k Sorted Lists https://youtu.be/q5a5OiGbT6Q?si=Oe5XE1QtO56CiD-s # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 입력으로 주어진 리스트가 비어 있거나, 리스트의 길이가 0일 경우 None 반환 if not lists or len(..

39. Combination Sum from typing import Listclass Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtrack(start, comb, total): # Base case: 합이 target과 같으면 결과에 추가 if total == target: res.append(comb.copy()) return # 합이 target을 초과하면 더 이상 탐색하지 않음 if tot..

77. Combinations https://youtu.be/q0s6m7AiM7o?si=im6vNN9SG6FK35Vs 풀이 과정문제 이해:n: 1부터 n까지의 숫자.k: 조합에 포함할 숫자의 개수.조합은 순서가 중요하지 않음.백트래킹 전략:숫자 1부터 n까지 반복하며 k개의 숫자를 선택.선택된 숫자는 조합에 추가.조합이 k개의 숫자를 만족하면 결과에 추가.선택한 숫자를 다시 되돌려가며 새로운 조합을 탐색.최적화:현재 숫자 iii를 선택한 뒤에는 i+1부터 탐색.중복된 조합 생성을 방지.class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] # 결과를 저장할 리스트 # 백트래킹 함수 정의 ..

212. Word Search II https://leetcode.com/problems/implement-trie-prefix-tree/description/ : 208. Implement Trie (Prefix Tree) https://youtu.be/asbcE9mZz_U?si=7ovXqcPW-mJDtg7h   class TrieNode: def __init__(self): self.children = {} # 자식 노드를 저장하는 딕셔너리 (예: {'a': TrieNode()}) self.isWord = False # 현재 노드가 단어의 끝인지 여부를 나타내는 플래그 def addWord(self, word): cur = self # 현재 노드에..

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 으로 넣고 # 여기서 발란스는 ..