효팍이의 프로그래밍

백준 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..

백준 1068번 트리 백준 1068번 트리 설명 부모노드의 리스트, 지울 노드로 dfs를 호출한다. 지울 노드 값의 부모 리스트를 -2로 바꾸고 부모 리스트를 돌면서 지울노드가 있는지 찾는다. 있으면 지울 노드의 자식 노드들이 있다는 말이기 때문에 그 값을 지울 노드로 해서 dfs를 호출해서 그 값을 -2로 바꿔준다. 이렇게 하면 지울노드와 그 자식노드 모두다 그 위치에 부모노드 리스트에 -2가 박힌다. 그 다음 부모 노드 리스트 인덱스로 쭈욱 돌면서 그 값이 -2가 아니고, 인덱스가 부모리스트에 아에 없는 값이 있으면 count를 1 증가 시키고, count가 정답 인덱스가 부모 리스트에 없으면 그 인덱스를 부모로 가지는 자식이 없다는 말이기 때문에 그 인덱스는 리프노드임 코드 import sys fr..

백준 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..

문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 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 트리 트리는 순환 구조를 갖지 않..