hyunkookim 님의 블로그

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 # 이미 계산..

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] # 부분 문자열 추출 ..

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

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

300. Longest Increasing Subsequence https://youtu.be/cjWnW0hdF1Y?si=DCsJr16gb5K6nTle class Solution: def lengthOfLIS(self, nums: List[int]) -> int: """ n = len(nums) dp = [0] * n, nums 개수만큼 우선, 초기값으로 dp[n-1] = 1 왜냐, 마지막은.. 자기자신.. dp[m] = max(1, 1 + dp[m+1] if nums[m] 이 문제는 "Longest Increasing Subsequence (LIS)", 즉 최장 증가 부분 수열 문제입니다. 아래에서..

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

427. Construct Quad Tree https://youtu.be/UQ-1sBMV0v4?si=5BBkFUGx3Q4HoIeF """# Definition for a QuadTree node.class Node: def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight): self.val = val # 현재 노드의 값 (0 또는 1) self.isLeaf = isLeaf # 현재 노드가 리프 노드인지 여부 self.topLeft = topLeft # 왼쪽 위 서브노드 self.topRight = topRight # 오른쪽 위 서브노드 self.bot..

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