몽상실현개발주의

[BOJ] 1967 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다. 다시 복습하자면, Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx..

[BOJ] 1167 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 Tree 의 지름을 구하는 문제이다. 문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다. Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx를 잡..

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 node의 root를 찾는 문제이다. 최상단의 root 노드가 항상 1로 시작하기 때문에, 모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): f, t = map(int, inpu..

[알고리즘 기초] 07_Tree / Python Tree 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 트리의 정의 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다 노드 중 최상위 노드를 root 라 한다. 나머지 노드들은 n(>=0) 개의 분리 집합 T1, ..., TN 으로 분리될 수 있다. 이들 T1, ..., TN 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리 (subtree)라 한다. 트리의 용어 노드(node) - 트리의 원소 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트..