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"의 부분 ..

Problem 1: Minimum Spanning Tree설명: 주어진 그래프에서 최소 신장 트리를 찾습니다.핵심 개념: 그래프, 최소 신장 트리, 크루스칼 알고리즘, 유니온 파인드.링크: LeetCode 1000Problem 2: Minimum Cost to Hire K Workers설명: K명의 노동자를 고용하는 최소 비용을 계산합니다.핵심 개념: 그리디 알고리즘, 우선순위 큐.링크: LeetCode 857Problem 3: Minimum Cost to Merge Stones설명: 주어진 돌들을 하나로 합치는 최소 비용을 계산합니다.핵심 개념: 동적 계획법, 누적 합.링크: LeetCode 1000Problem 4: Minimum Cost to Make at Least One Valid Path in..

Problem 1: Minimum Cost to Connect Sticks설명: 주어진 막대들을 모두 연결하는 데 필요한 최소 비용을 계산합니다.핵심 개념: 그리디 알고리즘, 우선순위 큐.링크: LeetCode 1167Problem 2: Path With Minimum Effort설명: 2D 그리드에서 시작점부터 도착점까지 이동할 때, 경로의 최대 고도 차이가 최소가 되는 경로를 찾습니다.핵심 개념: 그래프, 최소 신장 트리, 다익스트라 알고리즘.링크: LeetCode 1631Problem 3: Connecting Cities With Minimum Cost설명: 도시들을 연결하는 도로의 비용이 주어질 때, 모든 도시를 연결하는 최소 비용을 계산합니다.핵심 개념: 최소 신장 트리, 크루스칼 알고리즘, 유..

간선에 방향이 없는 그래프에서"최소 비용 신장 트리(Minimum Spanning Tree: MST)"를 찾는 방법신장 트리(Spanning Stees)간선에 방향이 없는 그래프에서 신장 트리는 모든 정점들을 연결 할 수 있는 트리를 의미부분 그래프가 아니라 부분 트리(tree) 임트리에는 싸이클이 포함될 수가 없음그래서, 어떤 그래프의 신장트리는 여러가지가 될 수 있다는 의미    A   /  \  B -- C  이건 그래프: 정점3개, 간선 3개    A   /  \  B    C  이건 트리: 정점3개, 간선 2개     A   /    B -- C  이건 트리: 정점3개, 간선 2개    A      \  B -- C  이건 트리: 정점3개, 간선 2개"최소 비용 신장 트리" 로 개념 확장: 간선..