본문 바로가기

Tree

[BOJ] 백준 13244번 Tree (Java)
Dot Algo∙ DS/PS 2021. 12. 14. [BOJ] 백준 13244번 Tree (Java) #13244 Tree 난이도 : 골드 4 유형 : 그래프 / 트리 / Union-Find 13244번: Tree For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise. www.acmicpc.net ▸ 문제 One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees. Trees are the subset of graphs that have th..
[BOJ] 백준 1068번 트리 (Java)
Dot Algo∙ DS/PS 2021. 6. 2. [BOJ] 백준 1068번 트리 (Java) #1068 트리 난이도 : 골드 5 유형 : 그래프 / BFS/ DFS 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ▸ 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과..
[BOJ] 백준 1949번 우수 마을 (Java)
Dot Algo∙ DS/PS 2021. 5. 25. [BOJ] 백준 1949번 우수 마을 (Java) #1949 우수 마을 난이도 : 골드 1 유형 : 트리 순회/ DP 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net ▸ 문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있..
[자료구조] BinaryTree 정리 (Java)
Dot Algo∙ DS/자료구조 2021. 4. 9. [자료구조] BinaryTree 정리 (Java) 트리 Tree, 비선형 자료구조 자료구조는 선형구조(Linear)와 비선형구조(NonLinear)로 구분된다. 트리(Tree)란, Array, LinkedList, Stack, Queue와 같이 선형 개념의 자료구조가 아니라 부모-자식 개념을 가지는 비선형 개념의 자료구조이다. 비선형 자료구조는 하나의 자료 다음에 순차적으로 데이터가 나열되어 있는 것이 아니라 여러개의 자료가 존재할 수 있음을 의미한다. 이진트리 BinaryTree 트리(Tree) 중 이진트리(BinaryTree)는 컴퓨터 응용에서 가장 많이 활용되는 아주 중요한 트리구조이다. 이진트리의 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것인데, 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있다. 다만 서브트리는 공..

티스토리툴바

티스토리툴바