pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 정렬 알고리즘 목록의 요소를 특정 순서대로 넣는 알고리즘 숫자식 순서(Numerical Order) / 사전식 순서(Lexicographical Order) 버블 정렬 이웃한 두 데이터의 대소비교를 n번 수행하는 알고리즘 시간복잡도 O(n2) def bubblesort(A): # (1) for i in range(1, len(A)): # (2) for j in range(0, len(a)-i): # (3) if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A[j] # (1) 2개씩 비교하니까 n-1번 수행 # (2) 0부터 매 루프마다 i개씩 뺀 범위에서 비교 수행 # (3) 앞 요소가 더 크면..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 리스트에 포함된 두 문자열이 더해져서 팰린드롬이 되는 문자열의 인덱스 pair들 출력 책에서 구현된 코드 import collections from typing import List # 트라이 저장할 노드 class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) self.word_id = -1 self.palindrome_word_ids = [] class Trie: def __init__(self): self.root = TrieNode() @staticmethod def is_palindrome(word: s..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 트라이 구현하기 책에서 구현된 코드 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 기억해야할 기법 구현보다 활용이 더 어려울듯 문제를 트리로 전환하여 떠올리는 것 문제의 요구사항을 그림으로 떠올리는 것 그 그림이 중위순회를 의미한다는 것을 캐..