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

91. Decode Ways https://youtu.be/6aEyTjOwlJU?si=gOHrfB_eRCdonSuR class Solution: def numDecodings(self, s: str) -> int: dp = {len(s) : 1} def dfs(i): if i in dp: return dp[i] if s[i] == "0": return 0 res = dfs(i+1) if (i+1  class Solution: def numDecodings(self, s: str) -> int: dp = {len(s) : 1} ..

2466. Count Ways To Build Good Strings https://youtu.be/JKpVHG2mhbk?si=3Ak7-dfYaYnRK9AZ class Solution: def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int: mod = 10**9 + 7 dp = {} def dfs(length): if length > high: return 0 if length in dp: return dp[length] # if low = low else 0 ..

2140. Solving Questions With Brainpower class Solution: def mostPoints(self, questions: List[List[int]]) -> int: # brainpower[i]는 해당 문제를 푼 후 건너뛰어야 하는 문제의 개수를 의미 # 즉, 문제 i를 풀기로 선택하면, # 그 다음 연속된 brainpower[i]개의 문제는 풀 수 없음 n = len(questions) dp = [0] * (n+1) # dp[i]는 질문 i부터 끝까지 얻을 수 있는 최대 점수 for i in range(n - 1, -1, -1): # 역순으로 순회 point, b..

474. Ones and Zeroes https://youtu.be/miZ3qV04b1g?si=ieg8qGyjhzei0dQq class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) -> int: # memoization dp = {} # 메모이제이션을 위한 딕셔너리 생성, 키는 (i, m, n), 값은 최대 부분집합 크기 def dfs(i, m, n): if i == len(strs): # 문자열 리스트를 모두 탐색했을 경우 return 0 # 부분집합을 더 이상 추가할 수 없으므로 0 반환 if (i, m, n) in ..

377. Combination Sum IV https://youtu.be/dw2nMCxG0ik?si=yplgrcGvhUBBlT9w class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: # bottom-up dp # nums = [num1, num2, num3, ...] # dp[0] = 1 # dp[1] = ? # dp[2] = ? # dp[3] = ? # dp[target] = dp[target-num1] + dp[target-num2] + dp[target-num3] + ... dp = {0:..

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

279. Perfect Squares # 완전 제곱수의 합이 n 이 되는 요소 개수 찾기 # 그런데 그 요소 개수가 최대한 적어야 해서. # 제곱수는 큰수로 이뤄저 있어야 하므로, 큰수부터 검색하는것이..# DP 또는 BFS 로 풀수 있음  1. Dynamic Programming (DP) 풀이  예제)class Solution: def numSquares(self, n: int) -> int: """ 문제 설명: 정수 n을 완전 제곱수들의 합으로 표현할 때, 필요한 최소 항의 개수를 구하는 문제. 완전 제곱수는 1, 4, 9, 16과 같은 수를 의미합니다. """ # DP 배열 초기화 # dp[i]는 숫자 i를..

337. House Robber III 노드 2개가 연결된것을 선택하면 안된다는 거니,=> 부모, 자식은 선택 못함,즉,1) 같은 레벨 끼리, 아니면,2) 나를 기준으로, 내 부모->내 자식 요렇게 문제에서 요구하는 내용은 다음과 같습니다:"부모-자식 관계에 있는 노드가 같은 날 털리지 않도록 해야 함":즉, 부모 노드와 직접 연결된 자식 노드 중 하나만 선택 가능.예를 들어, 한 노드를 선택하면 그 노드의 부모나 자식 노드는 선택할 수 없음."최대 금액을 구해야 함":각 노드의 값을 합산할 때 가능한 최대 금액을 계산.해결 방법 (Dynamic Programming + Tree Traversal)이 문제를 해결하기 위해 재귀적 접근법과 **DP (Dynamic Programming)**를 사용합니다.아..

95. Unique Binary Search Trees II https://youtu.be/m907FlQa2Yc?si=0uoBNIz-4bKCMaD8 # 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]: # n개의 노드로 생성 가능한 모든 고유한 BST를 반환하는 함수 ..