pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 트라이 구현하기 책에서 구현된 코드 import collections # 트라이의 노드 class TrieNode: def __init__(self): self.word = False self.children = collections.defaultdict(TrieNode) class Trie: def __init__(self): self.root = TrieNode() # 단어 삽입 def insert(self, word: str) -> None: node = self.root for char in word: node = node.children[char] node.word = True # 단어 존재 여부 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 트라이 검색 트리의 일종 일반적으로 키가 문자열 동적 배열 또는 연관 배열을 저장 정렬된 트리 자료구조 특징 다진 트리 (m-ary Tree) 문자 단위로 색인을 구축하는 것과 흡사 수 백개의 문자 중 apple 단어의 존재를 5번 만에 찾음

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 정렬되지 않은 배열에서 K번째 큰 요소 추출 책에서 구현된 코드 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return sorted(nums, reverse=True)[k - 1] 기억해야할 기법 정렬이 더 빠르다 heapify해서 K번째 요소를 찾는 것보다 정렬이 더 빠르다고 한다 내가 구현한 코드 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heapq.heapify(nums) k = len(nums)-k+1 while k != 1..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 힙의 특성을 만족하는 거의 완전한 트리(Almost Complete Tree)인 트리 기반 자료구조 힙의 특성 - 부모가 항상 자식보다 작거나 같다 거의 완전한 트리 - 완전 트리(Complete Tree)와 같은 의미 - 포화 트리(Perfect Tree)에서 pefect와 complete의 단어적 의미 충돌로 인해 생겨난 말인듯 하다 https://en.wikipedia.org/wiki/Binary_tree Binary tree - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Limited form of tree ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 전위순회와 중위순회 정보로 이진 트리 만들기 책에서 구현된 코드 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: 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 기억해야할 기법 중간값(이진탐색)에서의 범위..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 그래프의 최소 신장 트리가 되는 루트 출력 책에서 구현된 코드 class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: if n 2: n -= len(leaves) new_leaves = [] for leaf in leaves: neighbor = graph[leaf].pop() graph[neighbor].remove(leaf) if len(graph[neighbor]) == 1: new_leaves.append(neighbor) leaves = new_leaves return leaves 기억해야할 ..