hyunkookim 님의 블로그

646. Maximum Length of Pair Chain class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: # right 기준으로 오름차순 정렬 pairs = sorted(pairs, key=lambda x: x[1]) print(pairs) # 이전꺼의 r 보다 다음거의 l 가 작거나 같으면 추가 안함 right = pairs[0][1] res = [pairs[0]] for i in range(1, len(pairs)): if right

673. Number of Longest Increasing Subsequence https://youtu.be/Tuc-rjJbsXU?si=n0lvzu2hxl6XtygW class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: # DP를 사용하는데, # lenLIS: LIS 길이도 저장해야되고, # Count: LIS 개수도 저장해야 함 """ i | 0 | 1 | 2 | 3 | 4 | nums | 1 | 3 | 5 | 4 | 7 | lenLIS ..

712. Minimum ASCII Delete Sum for Two Strings 이 문제는 두 문자열을 같게 만들기 위해 삭제해야 하는 문자들의 ASCII 값 합을 최소화하는 문제입니다. 이를 해결하기 위해 **동적 계획법(Dynamic Programming)**을 사용할 수 있습니다.문제 분석주어진 문자열:s1="sea", s2="eat"목표:두 문자열을 같게 만들기 위해 삭제해야 하는 문자의 ASCII 값 합을 최소화.공통된 부분 수열은 유지하고 나머지 문자는 삭제.예제 분석:s1="sea", s2="eat"공통된 부분 수열은 "ea".삭제된 문자들:s1: "s"(115)s2: "t" (116)결과: 115+116=231.class Solution: def minimumDeleteSum(sel..

516. Longest Palindromic Subsequence https://youtu.be/bUr8cNWI09Q?si=5OUyGmMcZAuUGtkC 1) LCS로 푸는 법원래 문자열과 뒤집은 문자열의 LCS 는 Longest Palindromic Subsequence 임 Palindromic string: 읽었을때, 앞으로 읽으나 뒤로 읽으나 같은 문자열LCS(Longest Common Subsequence): 두 문자열에서 순서를 유지하면서 가장 긴 공통 부분 수열을 찾는 문제를 말합니다. 부분 수열 (Subsequence):문자열에서 몇 개의 문자를 순서를 유지하면서 선택한 부분 문자열.반드시 연속할 필요는 없지만, 문자들의 순서는 원래 문자열과 같아야 합니다.예:문자열 "ABCDEF"의 부분 ..

931. Minimum Falling Path Sum class Solution: def minFallingPathSum(self, matrix: List[List[int]]) -> int: # nxn 배열 # 3방향으로 떨어질수 있음. => 3방향으로 올라갈수 있다는 의미 # 계산 다해서, 제일 윗 열중, 최소값 찾으면 됨 N = len(matrix) # 이것도 역순으로.. 아래에서->위로, # 그런데, 제일 아래줄은 계산에는 반영해도 # 루프에는 빼기 for r in range(N-2, -1, -1): for c in range(N): ..

740. Delete and Earn 코드 설명문제 핵심 이해:특정 숫자를 선택하면 해당 숫자 * 빈도수를 점수로 얻습니다.그러나 선택한 숫자 (n)에 대해 (n−1)과 (n+1)은 선택할 수 없습니다.해결 전략:정렬 및 DP를 사용하여 숫자를 순차적으로 탐색.earn1과 earn2를 사용하여 이전 상태를 추적.earn1: 두 칸 이전의 최대 점수.earn2: 한 칸 이전의 최대 점수.동작 원리:현재 숫자와 이전 숫자가 연속되지 않는 경우:earn2 = earn2+curEarn  (현재 점수를 그대로 추가).현재 숫자와 이전 숫자가 연속된 경우:earn2=max⁡(earn1+curEarn, earn2)(현재 숫자를 포함한 점수와 포함하지 않은 점수 중 최대값 선택).최종 반환:모든 숫자를 탐색한 후 얻을..

509. Fibonacci Number class Solution: def fib(self, n: int) -> int: if n

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