pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 전위순회와 중위순회 정보로 이진 트리 만들기 책에서 구현된 코드 class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if inorder: # 전위 순회 결과는 중위 순회 분할 인덱스 index = inorder.index(preorder.pop(0)) # 중위 순회 결과 분할 정복 node = TreeNode(inorder[index]) node.left = self.buildTree(preorder, inorder[0:index]) node.right = self.buildTree(preorder,..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 로그 재정렬 기준 책에서 구현된 코드 class Solution: def isBalanced(self, root: TreeNode) -> bool: def check(root): if not root: return 0 left = check(root.left) right = check(root.right) # 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가 if left == -1 or \ right == -1 or \ abs(left - right) > 1: return -1 return max(left, right) + 1 return check(root) != -1 기억해야할 기법 DFS에..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 직렬화 / 역직렬화 구현 책에서 구현된 코드 class Codec: # 직렬화 def serialize(self, root: TreeNode) -> str: queue = collections.deque([root]) result = ['#'] # 트리 BFS 직렬화 while queue: node = queue.popleft() if node: queue.append(node.left) queue.append(node.right) result.append(str(node.val)) else: result.append('#') return ' '.join(result) # 역직렬화 def deserializ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 트리의 child들을 모두 반전 책에서 구현된 코드 class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root: root.left, root.right = \ self.invertTree(root.right), self.invertTree(root.left) return root return None 기억해야할 기법 단순 swap도 재귀로 구현 재귀가 일어난 시점에서 어떤 연산이나 복잡한 과정이 필수적인 사항은 아님 놀랍게 깔끔하다 내가 구현한 코드 class Solution: def invertTree(self, root: TreeN..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 이진 트리에서 두 노드의 가장 긴 경로 길이 출력 책에서 구현된 코드 class Solution: longest: int = 0 def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(node: TreeNode) -> int: if not node: return -1 # 왼쪽, 오른쪽 각각 리프 노드까지 탐색 left = dfs(node.left) right = dfs(node.right) # 가장 긴 경로 self.longest = max(self.longest, left + right + 2) # 상태값 return max(left, right) ..