hyunkookim 님의 블로그

215. Kth Largest Element in an Array class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # minheap 으로 만들고, k개 까지. 힙 개수 유지하게 하면, # k 개 보다 많으면 작은 것들 제거 # 그렇게 하면, minheap[0]에는 k번째 큰 것이 남아있음 heapq.heapify(nums) while( len(nums) > k): heapq.heappop(nums) return nums[0] 메모리 절약을 위해, k 개 만큼 우선 넣어서, minheap 만들고.1개씩 추가해서, k개 넘는..

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)**으로 해결할 수 있습니다.각각의 거래 상태를 정의하고, 이를 기반으로 계산합니다. 상태 추적..

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