hyunkookim 님의 블로그

간선에 방향이 없는 그래프에서"최소 비용 신장 트리(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개"최소 비용 신장 트리" 로 개념 확장: 간선..

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

1. 피보나치 수열 (Fibonacci Sequence) - 1. 피보나치 수열 및 변형 문제 Problem 1: Fibonacci Number (LeetCode 509)설명: 피보나치 수열의 n번째 값을 계산합니다.핵심 개념: 재귀, 메모이제이션, 동적 계획법.링크: LeetCode 509Problem 2: 피보나치 수 5 (BOJ 10870)설명: n번째 피보나치 수를 구하는 문제입니다.핵심 개념: 재귀, 동적 계획법.링크: BOJ 108702. 계단 오르기 (Climbing Stairs) - 1. 피보나치 수열 및 변형 문제 Problem 3: Climbing Stairs (LeetCode 70)설명: n개의 계단을 오르는 방법의 수를 계산합니다.핵심 개념: 동적 계획법, 피보나치 수열.링크: Le..

벨먼-포드 알고리즘 (Bellman-Ford Algorithm)Easy (5):Find the Town Judge (LeetCode 997)설명: 마을의 판사를 찾는 문제로, 그래프 탐색의 기본 개념을 연습할 수 있습니다.핵심 개념: 그래프 탐색, 신뢰 관계 분석.Flood Fill (LeetCode 733)설명: 이미지 처리에서 시작하여 연결된 영역을 채우는 문제로, 그래프 탐색의 기초를 다질 수 있습니다.핵심 개념: 그래프 탐색, DFS/BFS.Number of Islands (LeetCode 200)설명: 그리드에서 섬의 개수를 세는 문제로, DFS/BFS를 활용한 그래프 탐색을 연습할 수 있습니다.핵심 개념: 그래프 탐색, DFS/BFS.Max Area of Island (LeetCode 695)..

다익스트라 알고리즘 (Dijkstra Algorithm)Easy (5):Network Delay Time (LeetCode 743)설명: 네트워크에서 신호가 모든 노드에 도달하는 데 걸리는 시간을 계산합니다.핵심 개념: 다익스트라 알고리즘, 그래프 탐색.Cheapest Flights Within K Stops (LeetCode 787)설명: 주어진 경유 횟수 내에서 가장 저렴한 항공편을 찾습니다.핵심 개념: 다익스트라 알고리즘, 우선순위 큐.Path With Minimum Effort (LeetCode 1631)설명: 지형의 높이 차이를 최소화하는 경로를 찾습니다.핵심 개념: 다익스트라 알고리즘, 최소 스패닝 트리.Minimum Cost to Reach Destination in Time (LeetCod..

IndexMinPQ를 Python으로 구현 IndexMinPQ의 구성과 주요 기능이 클래스는 인덱스 기반 최소 우선순위 큐를 구현합니다. 이를 통해 인덱스를 기반으로 효율적으로 원소를 삽입, 삭제, 변경할 수 있습니다.    class IndexMinPQ: def __init__(self, capacity): """ 우선순위 큐를 초기화합니다. :param capacity: 큐의 최대 크기 """ self.capacity = capacity # 최대 용량 self.size = 0 # 현재 큐에 있는 원소의 수 self.keys = [None] * (capacity + 1) # 우선순위를 저장하는 리스트 (1..

순회 방법 정리Pre-order Traversal (전위 순회):방문 순서: 루트 -> 왼쪽 -> 오른쪽전위 순회 결과: [1, 2, 4, 5, 3]Post-order Traversal (후위 순회):방문 순서: 왼쪽 -> 오른쪽 -> 루트동일한 트리에서 후위 순회 결과: [4, 5, 2, 3, 1]In-order Traversal (중위 순회):방문 순서: 왼쪽 -> 루트 -> 오른쪽동일한 트리에서 중위 순회 결과: [4, 2, 5, 1, 3] 후위 순회의 역순은후위 순회(Post-order Traversal)를 수행한 뒤, 그 결과를 뒤집은 순서를 의미합니다. 후위 순회(Post-order Traversal)순서: 왼쪽 -> 오른쪽 -> 루트예: 트리 노드의 값이 1, 2, 3, 4, 5라고 하면 후..

1. 기본 DP (One-Dimensional DP)Easy ProblemsProblem 1: Fibonacci Number (LeetCode 509)설명: 피보나치 수열의 nnn번째 값을 계산합니다.핵심 개념: DFS, 메모이제이션, 점화식.Problem 2: Climbing Stairs (LeetCode 70)설명: 계단을 1칸 또는 2칸씩 올라가며 nnn번째 계단에 도달하는 방법의 수를 구합니다.핵심 개념: DFS, DP-Bottom-Up, 점화식.Problem 3: Min Cost Climbing Stairs (LeetCode 746)설명: 계단을 오르는 최소 비용을 구합니다.핵심 개념: DP 배열, 점화식.Problem 4: Maximum Subarray (LeetCode 53)설명: 연속된 서..