hyunkookim 님의 블로그

2218. Maximum Value of K Coins From Piles https://youtu.be/ZRdEd_eun8g?si=nPvl34N3ezdyQO58 백트래킹 솔루션 : 테스트는 통과하나, 시간 제한에 걸림class Solution: def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int: n = len(piles) def dfs(i, coins): if i == n: # 범위 벗어나서. i 는 piles 의 index return 0 res = dfs(i+1, coins) # skip current pile curP..

1220. Count Vowels Permutation https://youtu.be/VUVpTZVa7Ls?si=ebIzPzi9iQeVkNQa class Solution: def countVowelPermutation(self, n: int) -> int: """ Permutation: 순열 / Permutation 아래 규칙을 따르는 n 길이의 순열 개수 계산: Calculate the number of permutations of length `n` following these rules: - 문자열은 a, e, i, o, u로만 구성 / The string consists of only 'a', 'e', 'i', 'o', 'u'. ..

265. Paint House II class Solution: def minCostII(self, costs: List[List[int]]) -> int: N = len(costs) K = len(costs[0]) for n in range(N-1-1, -1, -1): for k in range(K): costs[n][k] += min([costs[n+1][i] for i in range(K) if i != k]) return min(costs[0])

256. Paint House 내 풀이 (맞춤)class Solution: def minCost(self, costs: List[List[int]]) -> int: n = len(costs) dp = [[0]*3 for _ in range(n)] dp[-1][:] = costs[-1][:] if n > 1: for r in range(n-1-1, -1, -1): for c in range(3): dp[r][c%3] = min(dp[r+1][(c+1)%3], dp[r+1][(c+2)%3]) + costs[r][c%3] #print(dp) ..

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

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