효팍이의 프로그래밍

백준 4256번 트리 백준 4256번 트리 설명 전위 순회는 가운데, 왼쪽, 오른쪽으로 가기 때문에 첫번째 값이 가운데 노드이므로 이 노드를 중위 순회에 적용하여 중위 순회를 가운데 노드 기준으로 왼쪽, 오른쪽으로 나누는 분할 정복 형태로 문제를 풉니다. 이렇게 트리를 만들고, 후위 순회로 찍어줍니다. 코드 import sys from typing import List input = sys.stdin.readline # 트리 구조체 선언 class TreeNode: def __init__(self, x, left=None, right=None): self.x = x self.left = left self.right = right class Solution: def tree(self, preorder: L..

백준 1167번 트리의 지름 백준 1167번 트리의 지름 아무점을 잡고 dfs로 가장 거리가 먼 정점을 찾는다. 이 정점을 기준으로 다시 dfs로 가장 먼 거리를 찾는다. 코드 from typing import List, Tuple import sys import collections input = sys.stdin.readline sys.setrecursionlimit(10**6) class Solution: def diameter(self, V: int, graph: List[List[Tuple]]): def dfs(u, count): visited[u] = True for v, w in graph[u]: if not visited[v]: vertex, weight = dfs(v, count+w) i..

백준 1967번 트리의 지름 백준 1967번 트리의 지름 루트에서 리프노드까지 탐색해서 최대 거리인 리프노드를 구하면 그 리프노드는 최대 거리에서의 한 점이 된다. 그 리프노드에서 다른 리프노드까지의 거리를 구하고 거기서 최대 값을 뽑아낸다. 루트 노드에서 간선이 한개밖에 없을때, 트리형태로 보면 루트노드가 리프노드처럼 보이므로 1번 최대 리프노드에서 루트까지의 거리도 고려해줘야함 코드 import sys import collections input = sys.stdin.readline graph = collections.defaultdict(list) n = int(input()) # n이 1일 때는 간선이 없으므로 0을 출력하고 종료 if n == 1: print(0) exit(0) # 리프노드 집합..

문제 트리의 전위, 중위 순회 결과를 입력값으로 받아 이진 트리를 구축하라. 전위 순회 결과: [3,9,20,15,7] 중위 순회 결과: [9,3,15,20,7] 결과는 밑의 그림과 같은 이진 트리가 된다. 코드 from typing import List class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if inorder: # 전위 순회 결과는 중위 순회 분할 인덱스 index = ino..

문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 2 입력 출력 2 코드 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode): def dfs(node: TreeNode): if node is None: return 0 left = dfs(node.left) right = dfs(node.right) if node.left and node.left.val == node.val: left += 1 else: l..

트리 트리는 재귀로 정의된 자기 참조 자료구조이다. 쉽게 말하면, 트리는 자식도 트리고 또 그 자식도 트리다. 즉 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 구성된다고 표현한다. 트리의 각 명칭 트리는 항상 루트에서부터 시작된다. 루트는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브 트리 구성을 띈다. 레벨은 0에서부터 시작한다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다. 일반적으로 간선의 방향은 위에서 아래로 향한다. 그래프 vs 트리 트리는 순환 구조를 갖지 않..