pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 로그 재정렬 기준 책에서 구현된 코드 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..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 로그 재정렬 기준 책에서 구현된 코드 class Solution: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: if t1 and t2: node = TreeNode(t1.val + t2.val) node.left = self.mergeTrees(t1.left, t2.left) node.right = self.mergeTrees(t1.right, t2.right) return node else: return t1 or t2 기억해야할 기법 return t1 or t2 둘 중 하나가 존재하면, 존재하는 객체 리턴 둘 다 존재하지 않는다면, Non..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 트리의 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: result: int = 0 def longestUnivaluePath(self, root: TreeNode) -> int: def dfs(node: TreeNode): if node is None: return 0 # 존재하지 않는 노드까지 DFS 재귀 탐색 left = dfs(node.left) right = dfs(node.right) # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가 if node.left and node.left.val == node.val: left += 1 else: left ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 이진 트리에서 두 노드의 가장 긴 경로 길이 출력 책에서 구현된 코드 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) ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 트리의 최대 깊이 출력 책에서 구현된 코드 def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 queue = collections.deque([root]) depth = 0 while queue: depth += 1 # 큐 연산 추출 노드의 자식 노드 삽입 for _ in range(len(queue)): cur_root = queue.popleft() if cur_root.left: queue.append(cur_root.left) if cur_root.right: queue.append(cur_root.right) # BFS 반복 횟..

1. 구글 파이썬 가이드 - Default Argument Values "파이썬 알고리즘 인터뷰"라는 책을 쭉 읽으면서 그냥 넘어가지 못한 구간이 있다. 구글 파이썬 스타일 가이드를 설명하던 중, 아래와 같은 글귀와 코드를 보여주었다. 함수의 기본 값으로 가변 객체(Mutable)를 사용하지 않아야 한다. # No def foo(a, b=[]): pass # No def foo(a, b: Mapping = {}): pass # Yes def foo(a, b=None): if b is None: b = [] # Yes def foo(a, b: Optional[Sequence] = None): if b is None: b = [] 위 코드에서 "No"라는 comment에 적힌 함수들을 사용하지말고, "Yes..