hyunkookim 님의 블로그

115. Distinct Subsequences 두 문자열 s, t가 주어질 때, s로부터 t를 만들 수 있는 서로 다른 subsequence의 개수를 구하세요.subsequence: 문자의 순서는 유지하면서, 일부 문자를 생략한 것각 문자는 한 번만 사용 가능📌 예시 1Input: s = "rabbbit", t = "rabbit"  Output: 3s에서 'b'가 3번 등장하기 때문에, 각각을 생략하는 방식으로 3가지 방법이 존재📌 예시 2Input: s = "babgbag", t = "bag"  Output: 5다양한 'b', 'a', 'g' 조합이 존재해서 총 5가지 방법으로 만들 수 있음🔧 핵심 개념: dp[i][j]의 의미표현의미dp[i][j]s[0:i]로 t[0:j]를 만들 수 있는 su..

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

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