pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 두 노드간 책에서 구현된 코드 class Solution: prev = -sys.maxsize result = sys.maxsize # 재귀 구조 중위 순회 비교 결과 def minDiffInBST(self, root: TreeNode) -> int: if root.left: self.minDiffInBST(root.left) self.result = min(self.result, root.val - self.prev) self.prev = root.val if root.right: self.minDiffInBST(root.right) return self.result 기억해야할 기법 트리의 탐색 순서에 대..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 로그 재정렬 기준 책에서 구현된 코드 # 1. 재귀 class Solution: def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int: def dfs(node: TreeNode): if not node: return 0 if node.val R: return dfs(node.left) return node.val + dfs(node.left) + dfs(node.right) return dfs(root) # 2. stack (DFS) class Solution: def ran..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 노드의 값을 현재 노드의 값보다 큰 모든 노드의 값의 합으로 변경 책에서 구현된 코드 class Solution: val: int = 0 def bstToGst(self, root: TreeNode) -> TreeNode: # 중위 순회 노드 값 누적 if root: self.bstToGst(root.right) self.val += root.val root.val = self.val self.bstToGst(root.left) return root 기억해야할 기법 구현보다 활용이 더 어려울듯 문제를 트리로 전환하여 떠올리는 것 문제의 요구사항을 그림으로 떠올리는 것 그 그림이 중위순회를 의미한다는 것을 캐..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 정렬된 리스트를 받아 균형 이진 검색 트리 만들기 책에서 구현된 코드 class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: if not nums: return None mid = len(nums) // 2 # 분할 정복으로 이진 검색 결과 트리 구성 node = TreeNode(nums[mid]) node.left = self.sortedArrayToBST(nums[:mid]) node.right = self.sortedArrayToBST(nums[mid + 1:]) return node 기억해야할 기법 중간값(이진탐색)에서의 범위..