hyunkookim 님의 블로그

115. Distinct Subsequences 이 문제는 문자열 s에서 문자열 t를 **부분 수열(subsequence)**로 만들 수 있는 서로 다른 방법의 수를 구하는 문제입니다.S의 부분 수열 = 문자열 T를 만드는 수 찾는 것이를 해결하기 위해 **동적 계획법(DP)**을 사용합니다.문제 이해부분 수열 (Subsequence):문자열의 일부 문자들을 선택해 순서를 유지하면서 생성된 새로운 문자열.예: s="rabbbit", t="rabbit"부분 수열로 t를 생성하는 방법:첫 번째 r, 첫 번째 a, 첫 번째 b, 두 번째 b, 첫 번째 i, 첫 번째 t....총 3가지 방법.목표:s에서 t를 생성하는 모든 부분 수열의 개수를 반환.시간 및 공간 복잡도시간 복잡도:O(m×n): DP 테이블 크기..

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개"최소 비용 신장 트리" 로 개념 확장: 간선..