분류 전체보기
5639_이진검색트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 자 이번에는 이진검색트리이다. 이진검색트리는 루트 노드가 왼쪽노드보다는 무조건 크고, 오른쪽 노드보다는 무조건 작은 수가 들어있는 트리이다. 결국 전위탐색이던 중위탐색이던 후위탐색이던 다른 탐색으로 찾으려면 왼쪽노드와 오른쪽 노드가 갈라지는 경계점과 루트노드를 찾아야 한다. 전위탐색으로 시작을 했으므로 값을 담아둔 해당 리스트에서 가장 앞의 값이 루트노드일 것이고, 해당 노드의 값보다..
2263_트리의 순회 (메모리초과 나온다면?)
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 이번에는 트리의 순회 문제였다. 트리 구조를 보면 특징이 하나있다. 바로 트리를 잘라서 봐도 트리구조란 것 이전 문제에서 본 트리를 잠깐 보자면, 하나의 큰 트리는 작은 트리로 쪼갤 수 있다. 지금은 A가 루트인 트리이지만 C가 최고위의 트리와 B가 최고위인 트리 두개가 합쳐진 형태라고도 볼 수 있다. 그리고 전위,중위,후위 탐색은 특징이 있다. 전위 : 루트 + 왼쪽 + 오른쪽 중위 : 왼쪽 + 루트 + 오른쪽 후위 : ..
1991_트리 순회
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 처음 보면 조금 헤맬 수 있는 문제이다. 트리 구조에 대해서 약간 공부를 하고 순회하는 법에 대해서 공부를 한 후 풀 수 있었다. 리스트를 통해 현재노드와 자식 노드들을 저장하는것까지는 생각을 했는데 순회방법을 몰라서 헤맸었다. 알고보니 결국 탐색을 위해선 dfs방식을 택하는데 이때 print해주는 위치에 따라서 전위,중위,후위탐색이 되는 것이었다. n = int(input()) tre..
1967_트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 저번 글에서 트리의 지름을 구했던 것과 같은 방식으로 구할 수 있다. import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [ [] for _ in range(n+1)] for _ in range(n-1): a,b,w = map(int,input().split()) ..
1167_트리의지름
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리구조를 활용한 문제이다. 만약 트리의 어떠한 노드를 무작위로 잡는다고 생각해보자. 그점에서 가장 먼 곳을 잡는다면 한방향으로만 갈수있는 트리방향 특성상 가장 하단이거나 가장 상단일 것이다. 그 점에서 다시 최장거리를 구한다면 결국 트리전체구조의 최장거리를 구할 수 있다. import sys from collections import deque input = sys.stdin.r..
11725_트리의 부모 찾기
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리란 그래프의 일종인데, 중복된 곳에서 한 점으로 올 수 없는 구조이다. 해당 문제에서 트리구조를 찾기위해선, 먼저 연결관계를 모두 기록한 후에 1번 노드를 첫번째 부모로 둔 후, 자식들을 연결해 나가면 해결할 수 있다. import sys sys.setrecursionlimit(100000) input = sys.stdin.readline n = int(input()) tree = [ [] for _ in range(n + 1)] parents =[ 0 f..