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