Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 14244 트리 만들기
문제
n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오.
입력은 항상 정답이 존재하는 경우로만 주어지며 트리는 사이클이 없는 연결그래프, 리프는 차수가 1인 노드를 의미한다.
입력 및 출력
첫 번째 줄에 n과 m이 주어진다.
Tree
- 계층적인 자료를 표현하는데 적합한 자료구조.
- root노드와 subtree로 나누어져 있음
용어
- 차수: 노드와 연결된 간선의 개수
- 리프 노드: 자식 노드가 없는 노드
- level: 트리의 각 층에 번호를 매기는 것
- 높이: 트리의 최대 level
코드
풀이
- (n-m)개의 노드를 일렬로 세운다.
- (m-1)개의 노드를 단말 노드로 설정
→ root node + (m-1)개 단말노드 = m개의 리프
