hyunkookim 님의 블로그

300. Longest Increasing Subsequence https://youtu.be/cjWnW0hdF1Y?si=DCsJr16gb5K6nTle class Solution: def lengthOfLIS(self, nums: List[int]) -> int: """ n = len(nums) dp = [0] * n, nums 개수만큼 우선, 초기값으로 dp[n-1] = 1 왜냐, 마지막은.. 자기자신.. dp[m] = max(1, 1 + dp[m+1] if nums[m]  이 문제는 "Longest Increasing Subsequence (LIS)", 즉 최장 증가 부분 수열 문제입니다. 아래에서..

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라고 하면 후..