hyunkookim 님의 블로그

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

Ubuntu 20.04에서 NVIDIA CUDA 및 NCCL 관련 문제를 해결하려면 Ubuntu 20.04에 맞는 저장소와 GPG 키를 사용해야 합니다. 아래 단계를 따라 문제를 해결하세요.1. 기존 설정 제거잘못된 GPG 키와 저장소 설정을 제거합니다.bash코드 복사sudo rm -f /etc/apt/sources.list.d/cuda.list sudo rm -f /etc/apt/sources.list.d/nvidia-machine-learning.list sudo rm -f /usr/share/keyrings/nvidia-archive-keyring.gpg2. Ubuntu 20.04에 맞는 GPG 키 추가NVIDIA의 Ubuntu 20.04용 GPG 키를 추가합니다.GPG 키 다운로드:bash코드 ..

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

Easy 난이도Problem 1: Best Time to Buy and Sell Stock II (LeetCode 122)설명: 주어진 주식 가격 배열에서 여러 번의 거래를 통해 얻을 수 있는 최대 이익을 계산합니다.핵심 개념: 그리디 알고리즘, 주식 거래.링크: LeetCode 122Problem 2: Assign Cookies (LeetCode 455)설명: 아이들에게 쿠키를 나눠줄 때, 최대한 많은 아이들이 만족하도록 쿠키를 분배합니다.핵심 개념: 그리디 알고리즘, 정렬.링크: LeetCode 455Problem 3: Lemonade Change (LeetCode 860)설명: 레모네이드 가게에서 각 손님에게 거스름돈을 줄 수 있는지 확인하는 문제입니다.핵핵심 개념: 그리디 알고리즘, 거스름돈 문제..

Fractional Knapsack 및 유사 문제들(5문제) 이 문제들은 Fractional Knapsack과 유사한 논리와 알고리즘을 활용합니다.문제를 통해 그리디 알고리즘의 다양한 응용 방식을 연습할 수 있습니다. Problem 1: Maximum Units on a Truck (LeetCode 1710)설명: 다양한 종류의 상자가 주어졌을 때, 트럭에 실을 수 있는 최대 단위 수를 계산합니다. 각 상자 종류마다 상자의 수와 각 상자에 포함된 단위 수가 주어집니다.핵심 개념: 그리디 알고리즘, 정렬.링크: LeetCode 1710Problem 2: Minimum Cost to Hire K Workers (LeetCode 857)설명: 주어진 노동자들 중에서 최소한의 비용으로 K명의 노동자를 고용하는 ..

트리나 그래프에서 DP를 적용하는 문제들은 주로 다음과 같은 특징을 가지고 있습니다:트리 + DP 문제의 특징최적 하위 구조 (Optimal Substructure):각 노드에서의 최적 값(예: 최대 합, 최대 경로 길이 등)은 자식 노드들의 결과를 바탕으로 계산됩니다.예: Binary Tree Maximum Path Sum (LeetCode 124).DFS 기반 구현:트리의 구조를 탐색하며 하위 문제를 해결합니다.DFS(깊이 우선 탐색)로 트리를 순회하며 값을 업데이트합니다.예: 트리의 독립 집합 (Largest Independent Set).메모이제이션을 통한 중복 계산 방지:각 노드에서 계산한 값을 저장해 동일한 계산을 반복하지 않도록 합니다.예: Diameter of Binary Tree (Lee..