hyunkookim 님의 블로그

322. Coin Change https://youtu.be/H9bfqozjoqs?si=WXXZLGYu8Q1PKHbY class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # dp 개수: 0~amount 까지, 따라서, amount+1 개 생성 # dp[amount]: amount 만드는데 필요한 최소 동전 개수 dp = [amount+1] * (amount+1) dp[0] = 0 # 모든 금액에 대해서 최소 동전개수 계산 for a in range(1, amount+1): # dp[amount] 까지 for c in co..

139. Word Break 이 문제는 **Dynamic Programming (동적 프로그래밍)**을 사용해서 효율적으로 풀 수 있습니다."Word Break" 문제라고 불리는 전형적인 문제 중 하나입니다. 다음은 문제를 푸는 방법에 대한 자세한 설명입니다.문제 풀이 방법아이디어문자열 s를 특정 위치에서 쪼개서, 각 부분 문자열이 wordDict에 있는 단어로 구성되어 있는지 확인합니다.dp[i]를 정의: s[0:i]까지의 부분 문자열을 wordDict의 단어들로 분해할 수 있는지를 나타내는 boolean 값.기본 상태: dp[0] = True (빈 문자열은 항상 분해 가능).점화식dp[i] = True가 되려면, 아래 조건이 충족되어야 합니다:어떤 j(0 ≤ j 즉, dp[i] = dp[j] and ..

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)설명: 연속된 서..

70. Climbing Stairs https://youtu.be/Y0lT9Fck7qI?si=qZtxOINcvanqqhvu  class Solution: def climbStairs(self, n: int) -> int: # n 이 되기 위해, 1,2 로 구성된게 몇개?? # dfs # 트리.. # DP # cache + memorization # DP- bottom up """ dp[1] = 1 dp[2] = dp[1] + 1 dp[3] = dp[1] + dp[2] dp[4] = dp[3] + dp[2] dp[5] = dp[4] + dp[3] ..

427. Construct Quad Tree https://youtu.be/UQ-1sBMV0v4?si=5BBkFUGx3Q4HoIeF """# Definition for a QuadTree node.class Node: def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight): self.val = val # 현재 노드의 값 (0 또는 1) self.isLeaf = isLeaf # 현재 노드가 리프 노드인지 여부 self.topLeft = topLeft # 왼쪽 위 서브노드 self.topRight = topRight # 오른쪽 위 서브노드 self.bot..

23. Merge k Sorted Lists https://youtu.be/q5a5OiGbT6Q?si=Oe5XE1QtO56CiD-s # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 입력으로 주어진 리스트가 비어 있거나, 리스트의 길이가 0일 경우 None 반환 if not lists or len(..

148. Sort List https://youtu.be/TGveA1oFhrc?si=rRYsC927YCXjnEcg # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # time: n log n => merge sort # memory: O(1) => can Recursion, 재귀 if not head or..

1. DFS 성질을 이용한 연결 요소 탐색Easy 난이도Problem 1: Number of Islands (LeetCode 200)설명: 2D 그리드에서 '1'로 표시된 섬의 개수를 찾는 문제입니다. DFS를 사용하여 연결된 '1'들을 탐색해 섬의 개수를 계산합니다.핵심 개념: DFS, 2D 그리드 탐색Problem 2: Flood Fill (LeetCode 733)설명: 시작 픽셀과 연결된 모든 픽셀을 탐색하여 색을 변경하는 문제입니다. DFS를 통해 인접한 픽셀을 처리합니다.핵심 개념: DFS, 색칠 알고리즘Problem 3: Max Area of Island (LeetCode 695)설명: 2D 그리드에서 가장 큰 섬의 면적을 계산합니다. DFS로 연결된 '1'의 크기를 탐색합니다.핵심 개념: D..