알고리즘/트리
-
BOJ 7812 중앙 트리알고리즘/트리 2021. 3. 18. 20:55
www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 굉장히 재밌는 문제같아서 언젠간 풀어보려 했는데 이번에 풀게 되었다. 그냥 모든점에서 다익스트라를 돌리고 싶은 생각이 드는데, 생각해보면 그래프라 다익말고 dfs로도 최단거리가 나온다. 그런데 dfs 시간복잡도가 O(v)라서 v개의 정점에서 모두 dfs를 한번씩 돌려보면 O(v^2) = 시간초과 이다. 당연히 다른 방법이 필요하다. 이런 스타일의 문제는 대부분 dfs를 활용하면서, 인접한 ..
-
BOJ 14570 나무 위의 구슬알고리즘/트리 2021. 3. 18. 08:48
www.acmicpc.net/problem/14570 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net 이것도 처음 봤을 때는 못풀었다. 아니, 각 상황에 따라서 구슬이 내려가는 위치가 다른데, k가 10^18이라고? 분할정복도 아니고, 트리dp인가?? 하다가 못풀었던 문제인데 이제보니 이렇게 쉬울수가 없다... 규칙을 잘 생각해 보면 답이 나온다. 각 노드에서 구슬은 왼쪽 또는 오른쪽을 선택한다. 이 규칙에 의해서, 모든 상황에서 자식의 구슬개수는 1. 양쪽 자식의 자식의 구슬개수가 동일하거나 2. 왼쪽..
-
BOJ 2250 트리의 높이와 너비알고리즘/트리 2021. 3. 17. 19:01
www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제를 본 지는 좀 되었는데, 그당시에 뭔소린지 모르겠어서 못 풀었던 문제이다. 이번에 한번 더 보았는데, 너무 쉬운 문제였다. 왼쪽의 숫자는 노드의 깊이이고, 아래의 숫자는 inorder탐색을 했을때의 방문순서이다!! 따라서 이 문제는 그냥 노드의 깊이마다 inorder탐색을 제일 처음 만난 친구와 제일 늦게 만난 친구의 탐색순서의 차이를 출력하면 되는 문제이다. #include using ..
-
BOJ 12767 Ceiling Function알고리즘/트리 2021. 3. 17. 18:06
www.acmicpc.net/problem/12767 12767번: Ceiling Function Advanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer). www.acmicpc.net 영어 울렁증이 있는 나에게는 너무나 어려운 문제였다. 대충 트리를 구성하는 문제인건 알았는데, 트리 구성 조건이 다음과 같았다..