hyunkookim 님의 블로그

337. House Robber III 노드 2개가 연결된것을 선택하면 안된다는 거니,=> 부모, 자식은 선택 못함,즉,1) 같은 레벨 끼리, 아니면,2) 나를 기준으로, 내 부모->내 자식 요렇게 문제에서 요구하는 내용은 다음과 같습니다:"부모-자식 관계에 있는 노드가 같은 날 털리지 않도록 해야 함":즉, 부모 노드와 직접 연결된 자식 노드 중 하나만 선택 가능.예를 들어, 한 노드를 선택하면 그 노드의 부모나 자식 노드는 선택할 수 없음."최대 금액을 구해야 함":각 노드의 값을 합산할 때 가능한 최대 금액을 계산.해결 방법 (Dynamic Programming + Tree Traversal)이 문제를 해결하기 위해 재귀적 접근법과 **DP (Dynamic Programming)**를 사용합니다.아..

95. Unique Binary Search Trees II https://youtu.be/m907FlQa2Yc?si=0uoBNIz-4bKCMaD8 # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: # n개의 노드로 생성 가능한 모든 고유한 BST를 반환하는 함수 ..

96. Unique Binary Search Trees class Solution: def numTrees(self, n: int) -> int: # DP 배열 초기화 (Initialize the DP array) # dp[i]: i개의 노드를 사용하여 만들 수 있는 고유한 BST의 개수 # dp[i]: Number of unique BSTs that can be formed using i nodes dp = [0] * (n + 1) dp[0] = 1 # 빈 트리의 경우, 가능한 BST는 1개 (Empty tree has one valid BST) dp[1] = 1 # 노드가 1개인 경우, 가능한 BST는 1개 (One ..

from typing import Listclass Solution: def maxProfit(self, prices: List[int]) -> int: # 최대 이익을 계산해서, return # 언제든지 사고팔수 있지만, # 살려면. 기존 주식을 팔아야 하고 # 팔면 그다음날 cooldown 후, 그 다음날 살수 있음 """ root -> buy -> sell -> cooldown -> buy -> sell -> cooldown | -> cooldown -> cooldown -> buy -> cooldown ..

1312. Minimum Insertion Steps to Make a String Palindrome class Solution: def minInsertions(self, s: str) -> int: # Palindrome: 앞뒤로 읽었을때 동일한 string # 최소로 추가해야 하는 문자 개수를 반환 # 이미 Palindrome 이면 0 반환 # 그럼 우선 Palindrome 인지 체크하고 if s == s[::-1]: # Palindrome 이면 return 0 # 아니면 # s 와 뒤집은 s, 즉 reverse_s 의 LCS 최고로 긴 공통 문자열 찾아서, ..

1035. Uncrossed Lines class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: # 가장 긴 공통 수열 길이 찾는 것과 동일 len1 = len(nums1) len2 = len(nums2) dp = [[0] * (len2+1) for _ in range(len1+1)] for i in range(1, len1+1): for j in range(1, len2+1): if nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-..

1964. Find the Longest Valid Obstacle Course at Each Position from typing import Listimport bisectclass Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]: # LIS 구하는데, 단, 같아도 됨,    https://youtu.be/Xq9VT7p0lic?si=SPzorVE4gw3o4RNY

354. Russian Doll Envelopes class Solution: def maxEnvelopes(self, envelopes: List[List[int]]) -> int: # DP로 풀어야 함 # 안에 들어가려면, 가로, 세로 둘다 다른것보다 작아야 함 # 우선 정렬하고 # envelope 리스트에는 계속 포함되는 거는 계속 추가하고 # max_width, max_height 최대로 업데이트.. # LIS 풀듯이 풀어보자! envelopes = sorted(envelopes, key=lambda k:(k[0], k[1])) # 자신 포함이니 1로 초기화 dp =..

1027. Longest Arithmetic Subsequence class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: # longestArithSeq 는 같은 간격을 같는 LIS 를 찾는 거라서. # 즉, "등차수열을 이루는 가장 긴 부분 수열의 길이" # 해쉬맵에 lenLIS 와 간격 difference 를 저장해야 할듯 dp = {} # 키: (index, difference) -> 값: 등차수열의 길이 max_len = 1 # 최소 길이는 1 for i in range(len(nums)): # 정방향 순회 for j in..

1218. Longest Arithmetic Subsequence of Given Difference class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: # 주어진 배열 arr에서 # 차이가 difference인 '부분 수열(subsequence)'의 # 최대 길이를 찾는 것 dp = [1] * len(arr) res = -float("inf") for i in range(len(arr)-1, -1, -1): for j in range(i+1, len(arr)): if arr..