hyunkookim 님의 블로그

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

646. Maximum Length of Pair Chain class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: # right 기준으로 오름차순 정렬 pairs = sorted(pairs, key=lambda x: x[1]) print(pairs) # 이전꺼의 r 보다 다음거의 l 가 작거나 같으면 추가 안함 right = pairs[0][1] res = [pairs[0]] for i in range(1, len(pairs)): if right

673. Number of Longest Increasing Subsequence https://youtu.be/Tuc-rjJbsXU?si=n0lvzu2hxl6XtygW class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: # DP를 사용하는데, # lenLIS: LIS 길이도 저장해야되고, # Count: LIS 개수도 저장해야 함 """ i | 0 | 1 | 2 | 3 | 4 | nums | 1 | 3 | 5 | 4 | 7 | lenLIS ..