pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 트리 계층형 트리 구조를 시뮬레이션 하는 추상 자료형 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 - Recursively Defined Self-Referential - 즉, 트리는 자식도 트리, 그 자식도 트리 (서브트리) 트리의 명칭 차수 (Degree) - 자식 노드의 개수 크기 (Size) - 차수 + 자신을 포함(1) 깊이 (Depth) - 루트에서 현재 노드까지의 거리 높이 (Height) - 현재 노드에서 리프 노드까지의 거리 (가장 깊은) 그래프 vs 트리 트리는 순환(cycle)이 없어야 함 - 간선을 따라 탐색했을 때, 이미 탐색된 노드를 다시 만나지 않음 트리는 부모 -> 자식 단방..

BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 내가 작성한 코드 import sys, heapq read = sys.s..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 노드의 값을 현재 노드의 값보다 큰 모든 노드의 값의 합으로 변경 책에서 구현된 코드 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 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 기억해야할 ..