www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 아이디어: 이번에는 전위순회와 후외순회를 가지고 중위순회를 구하는 문제이다.. 앞선 문제와 비슷하게 풀 수 있을 것 같다. 전위순회는 제일 첫번째 원소가 루트니까 루트를 일단 찾으면 중위순회를 오른쪽, 왼쪽 서브트리로 나눌 수 있다. 그리고 후위순회는 루트를 제일 마지막에 출력하니까 배열에 순서대로 저장한 후 반대로 출력하면 될 것 같다. 익숙해지면 이 유형 문제는 빠르게 풀 수 있을 것 같다! #4..
알고리즘💻/트리
www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 아이디어: 이진트리 / 입력의 첫줄은 inorder = 중위순회, 둘째줄은 postorder = 후위순회.. -> 전위순회 구하기. 중위순회(LVR) 후위순회(LRV) -> 맨 마지막 원소가 루트. 전위순회(VLR) -> 후위순회에서 중위순회를 사용하여 루트를 순서대로 뽑아내면 된다. 중위순회는 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누어지므로, 후위순회[-1](루트)를 중위순회에서 찾고그 인덱스-1까지를 후위순회에서 잘라서 다시 ..
www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 아이디어: 트리의 지름에 대한 증명이 있다. 1. 트리에서 임의의 정점 x를 잡는다. 2. 정점 x에서 가장 먼 정점 y를 찾는다. 3. 정점 y에서 가장 먼 정점 z를 찾는다. -> y-z의 경로가 트리의 지름이다. 이 알고리즘? 정의? 를 이용해서 풀어보자. DFS와 재귀를 이용하여 구현했는데, 답은 제대로 나오는데 시간초과가 난다. pypy로 제출해도..ㅠㅠ import sys sys...
www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 아이디어: 모르겠어서 구글링했다. 전위순회니까 입력받는대로 노드를 삽입하면 그래프를 구할 수 있었다. 그.런.데. 정석대로(?) 풀면 파이썬은 시간 초과가 났다.. #시간초과 import sys sys.setrecursionlimit(10**9) class Node: def __init__(self, num): self.val = num self.left = None self.right = None..
www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 아이디어: 전위순회, 중위순회, 후위순회를 재귀로 구현하는 기본적인 문제이다. 중간에 if 문으로 '.'이 아닌 것을 확인해야 하는데, 처음에 이걸 print하기 전에만 해놔가지고 index에러가 났었다. import sys N = int(sys.stdin.readline()) graph = [[]for _ in range(N)] for _ in range(N): node, left, right = sys..
www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어: 그냥 시작하는 부분을 1로 하고 DFS 탐색을 하면서 부모노드를 저장해주면 되는 간단한 문제였다. import sys N = int(sys.stdin.readline()) graph = [[] for _ in range(N+1)] for _ in range(N-1): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) stack = [] stack.append(1) ..
www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 아이디어: 이거를 틀렸었나 보다.. 주어진 입력만 사용하지 말고 새롭게 child배열을 만들어서 풀면 간단히 풀 수 있는 문제였다. 일단 input의 부모배열을 가지고 child배열을 만들어 저장하고, 그 배열을 이용하여 DFS탐색을 한다. 이때 탐색하는 n이 삭제할 노드와 같다면 상황을 나누어야 하는데, n의 부모 노드의 자식이 n 하나 뿐이라면 부모노드도 리프노드가 되므로 cnt+=1을 해주고 그 외의..
