11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 분석 최소 공통 조상 임의의 두 노드를 선택 했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드(lowest common acestor) 최소 공통 조상 구하기 루트 노드에서 탐색을 시작해각 노드의 부모 노드와 깊이 저장 (DFS/BFS로 탐색) 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춤. 두 노드가 같으면 해당 노드가 공통 조..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 분석 트리 순회(전위 순회, 중위 순회, 후위 순회), DFS 1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 karla.tistory.com 풀이 import sy..

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 분석 최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과) 최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식 karla.tistory.com 풀이 """ 두 노드 쌍 M개 LCA 구하기 노드의 개수 N(2~100,000) N-1줄 트리상 연결된 두 노드 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 ..

➊ 특징 노드와 에지로 연결된 그래프의 특수한 형태 그래프의 표현으로도 트리를 표현할 수 있음 순환구조 X, 1개의 루트노드 루트노드를 제외한 노드는 1개의 부모노드를 가짐 트리의 부분 트리 역시 토리의 모든 특징을 따름 그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트) 간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리 karla.tistory.com ➋ 트리의 구성요소 구성요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결 관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노..