트리

CS/자료구조

[자료구조 및 프로그래밍] 7. 트리와 이진트리

2023.10.20

지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..

알고리즘 (PS)/BOJ

[백준] 14244- 트리 만들기 (S4)

2022.02.14

https://www.acmicpc.net/problem/14244 14244번: 트리 만들기 n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는 www.acmicpc.net 난이도는 쉽지 않아보이는데 의외로 쉽다. 알고리즘 분류에 나와있듯 트리를 이용한 구성적인 문제다. 트리가 어떻게 구성되는지 일반화 될 수 있는 규칙을 찾아 문제를 풀면 된다. 문제 조건에 의해 리프노드는 항상 최소 2개이고, 답이 항상 존재한다. 리프노드가 2개인 경우는 딱 한가지다. 모든 노드가 일직선으로 연결되면 된다. 리프노드가 3개 이상인 경우는 하나의 중심 노드에 대해 리프노드를 3개 ..

[자료구조 및 프로그래밍] 7. 트리와 이진트리

[백준] 14244- 트리 만들기 (S4)

티스토리툴바