hyunkookim 님의 블로그

5. Longest Palindromic Substring class Solution: def longestPalindrome(self, s: str) -> str: if len(s) == 1: return s # 문자열 길이가 1일 경우, 해당 문자열 반환 res = "" # 가장 긴 팰린드롬 문자열을 저장할 변수 for ln in range(1, len(s) + 1): # 부분 문자열 길이 탐색 for i in range(len(s) - ln + 1): # 시작 인덱스 탐색 substring = s[i:i + ln] # 부분 문자열 추출 ..

64. Minimum Path Sum class Solution: def minPathSum(self, grid: List[List[int]]) -> int: # grid의 행(row) 개수를 계산 rows = len(grid) # grid의 열(column) 개수를 계산 cols = len(grid[0]) # 첫 번째 열의 값을 누적합으로 업데이트 (위에서 아래로 이동) for r in range(1, rows): grid[r][0] += grid[r-1][0] # 현재 위치 값을 바로 위 값과 더함 # 첫 번째 행의 값을 누적합으로 업데이트 (왼쪽에서 오른쪽으로 이동) ..

120. Triangle https://youtu.be/OM1MTokvxs4?si=TThNXJkoqEIPcJsj  class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: # 삼각형의 아래에서 위로 계산 """ # bottom -> up 으로 가면서, min 계산 # 원래는 len(triangle)-1 시작이겠지만, # len(triangle)-1 이 마지막 단계니깐. # len(triangle)-2 부터 시작 """ for row in range(len(triangle) - 2, -1, -1): fo..

322. Coin Change https://youtu.be/H9bfqozjoqs?si=WXXZLGYu8Q1PKHbY class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # dp 개수: 0~amount 까지, 따라서, amount+1 개 생성 # dp[amount]: amount 만드는데 필요한 최소 동전 개수 dp = [amount+1] * (amount+1) dp[0] = 0 # 모든 금액에 대해서 최소 동전개수 계산 for a in range(1, amount+1): # dp[amount] 까지 for c in co..

139. Word Break 이 문제는 **Dynamic Programming (동적 프로그래밍)**을 사용해서 효율적으로 풀 수 있습니다."Word Break" 문제라고 불리는 전형적인 문제 중 하나입니다. 다음은 문제를 푸는 방법에 대한 자세한 설명입니다.문제 풀이 방법아이디어문자열 s를 특정 위치에서 쪼개서, 각 부분 문자열이 wordDict에 있는 단어로 구성되어 있는지 확인합니다.dp[i]를 정의: s[0:i]까지의 부분 문자열을 wordDict의 단어들로 분해할 수 있는지를 나타내는 boolean 값.기본 상태: dp[0] = True (빈 문자열은 항상 분해 가능).점화식dp[i] = True가 되려면, 아래 조건이 충족되어야 합니다:어떤 j(0 ≤ j 즉, dp[i] = dp[j] and ..

746. Min Cost Climbing Stairs class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: cost.append(0) for i in range(len(cost)-1-2, -1, -1): cost[i] += min(cost[i+1], cost[i+2]) return min(cost[0], cost[1]) https://youtu.be/ktmzAZWkEZ0?si=ovGzSVLU3LhGRQGh class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # 꼭대기를 0..

1137. N-th Tribonacci Number 내 풀이 class Solution: def tribonacci(self, n: int) -> int: T = [0] * 38 T[0] = 0 T[1] = 1 T[2] = 1 if n>2: for nn in range(3, n+1): T[nn] = T[nn-3]+T[nn-2]+T[nn-1] return T[n] 솔루션class Solution: def tribonacci(self, n: int) -> int: arr = [0, 1, 1] if n  3차: 2025.01.02(목): 해결함class ..

714. Best Time to Buy and Sell Stock with Transaction Fee https://youtu.be/cUsPoH5DG1Q?si=vWqiiqYgUO8o6U1N Code class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) # buy[i]: i번째 날에 주식을 구매한 상태에서의 최대 이익 # sell[i]: i번째 날에 주식을 판매한 상태에서의 최대 이익 buy = [0] * n sell = [0] * n # 초기값: # 첫 번째 날에 주식을 구매한 경우: -prices[0] ..