hyunkookim 님의 블로그

433. Minimum Genetic Mutation 이 문제는 그래프 탐색 문제로 생각할 수 있습니다.각각의 유효한 유전자 문자열(gene)을 노드로 보고,한 번의 변이로 연결될 수 있는 두 노드를 간선으로 연결하여최단 경로를 찾는 방식으로 해결합니다.문제의 주요 포인트유전자 변이의 정의:두 유전자 문자열에서 단 하나의 문자만 다른 경우, 한 번의 변이라고 간주합니다.예: "AACCGGTT" → "AACCGGTA" (1개의 문자만 변이).유효한 변이 조건:변이 후의 문자열은 반드시 bank에 포함되어 있어야 합니다. 그렇지 않으면 유효하지 않은 변이로 간주합니다.목표:startGene에서 endGene까지 변이를 통해 도달하기 위해 필요한 최소 변이 횟수를 계산합니다.도달할 수 없는 경우 -1을 반환합..

221. Maximal Square 이 문제는 m×n 크기의 **이진 행렬(binary matrix)**이 주어졌을 때,1로만 구성된 가장 큰 정사각형을 찾아 그 **면적(area)**을 반환하는 문제입니다.문제를 이해하기 위한 주요 포인트입력 형식:이진 행렬(matrix): m×n 크기의 리스트로, 각 원소는 문자열 "0" 또는 "1"입니다.목표:"1"로만 구성된 가장 큰 정사각형의 한 변의 길이를 구하고, 그 면적(한 변의 길이의 제곱)을 반환합니다.출력 형식:정사각형의 면적을 나타내는 정수 값.조건:정사각형은 반드시 연속된 1로 구성되어야 합니다. 해결 방법이 문제는 **동적 계획법(Dynamic Programming, DP)**을 사용하여 효율적으로 해결할 수 있습니다.핵심 아이디어dp[i][j]..

188. Best Time to Buy and Sell Stock IV 이 문제는 주어진 주식 가격 배열 prices에서 최대 k번의 거래를 통해 얻을 수 있는 최대 이익을 계산하는 문제입니다. 이 문제는 이전 문제들과 비슷하지만, 최대 k번의 거래를 허용한다는 점에서 확장된 형태입니다.문제 이해거래 정의:"거래"는 매수 후 매도를 의미합니다. 즉, 최대 k번의 거래를 할 수 있습니다.조건:거래는 동시에 진행할 수 없습니다. 즉, 매도 후에만 다시 매수할 수 있습니다.거래 횟수는 최대 k번입니다.목표:주어진 가격 배열에서 최대 k번의 거래를 통해 얻을 수 있는 최대 이익을 반환합니다.class Solution: def maxProfit(self, k: int, prices: list[int]) ->..

123. Best Time to Buy and Sell Stock III 문제 설명이 문제는 주어진 주식 가격 배열 prices를 기반으로 최대 두 번의 거래를 통해 얻을 수 있는 최대 이익을 찾는 문제입니다.조건:최대 두 번의 거래: 두 번의 매수/매도만 가능하며, 두 번째 거래는 첫 번째 거래가 완료된 후에만 가능합니다.동시 거래 금지: 주식을 보유한 상태에서 다시 매수할 수 없습니다. 즉, 먼저 매도 후에 새로운 거래를 시작해야 합니다.최대 이익 반환: 두 번의 거래를 통해 얻을 수 있는 최대 이익을 반환합니다.풀이 방법접근 방식이 문제는 동적 계획법(DP) 또는 **상태 추적(State Tracking)**으로 해결할 수 있습니다.각각의 거래 상태를 정의하고, 이를 기반으로 계산합니다. 상태 추적..

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)", 즉 최장 증가 부분 수열 문제입니다. 아래에서..