트리

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 이진 트리는 루트, 왼쪽 서브트리, 오른쪽 서브트리로 나눌 수 있습니다. 인오더와 포스트오더에서도 똑같이 3 부분으로 나눌 수 있습니다. 서브트리는 또다시 루트와 2개의 서브트리로 나눌 수 있습니다. 하나의 트리를 루트와 두 서브트리, 두 서브트리는 다시 루트와 서브트리로 나눌 수 있으며 이렇게 분할정복을 통해 문제를 해결할 수 있습니다. 예시를 들어서 구체적으로 설명해보겠습니다. 위와같은 트리가 주어졌을 때 인..

문제 3584번: 가장 가까운 공통 조상 (acmicpc.net) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 두 노드의 공통 조상을 찾는다면 부모 노드로 하나씩 거슬러 올라가며 부모가 같은 노드인지 확인하는 방법이 가장 간단합니다. 우선 부모가 같기 위해서는 루트로부터의 깊이가 같아야 합니다. 그렇기 때문에 주어진 두 노드의 깊이가 다르다면 깊이를 맞춰주는것이 우선입니다. 두 노드의 깊이가 같다면 동시에 하나씩 부모로 거슬러 올라가며 비교를 합니다..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리에서의 지름은 원과 마찬가지로 내부의 두 점 사이의 거리가 가장 먼 길이를 말합니다. 원에서 가장 먼 두 점은 원 둘레 위의 한 점에서 가장 먼 둘레위의 점입니다. 트리에서도 마찬가지로 적용할 수 있습니다. 리프노드에서 리프노드까지의 거리중 가장 먼 것을 구하면 됩니다. 한 노드에서 가장 먼 (리프)노드를 구하고, 그 노드에서 다시 가장 먼 (리프)노드까지의 거리를 ..