문제해결(PS)/ROSALIND

Counting Phylogenetic Ancestors

곰탱이장 2024. 9. 7. 10:45

https://rosalind.info/problems/inod/

 

ROSALIND | Counting Phylogenetic Ancestors

It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Counting Phylogenetic Ancestors solved by 3107 2012년 7월 2일 12:00:00 오전 by Rosalind Team Topics: Combinatorics, Phylogeny Culling the Fo

rosalind.info

Problem

A binary tree is a tree in which each node has degree equal to at most 3. The binary tree will be our main tool in the construction of phylogenies.

A rooted tree is a tree in which one node (the root) is set aside to serve as the pinnacle of the tree. A standard graph theory exercise is to verify that for any two nodes of a tree, exactly one path connects the nodes. In a rooted tree, every node vv will therefore have a single parent, or the unique node ww such that the path from vv to the root contains {v,w}{v,w}. Any other node xx adjacent to vv is called a child of vv because vv must be the parent of xx; note that a node may have multiple children. In other words, a rooted tree possesses an ordered hierarchy from the root down to its leaves, and as a result, we may often view a rooted tree with undirected edges as a directed graph in which each edge is oriented from parent to child. We should already be familiar with this idea; it's how the Rosalind problem tree works!

Even though a binary tree can include nodes having degree 2, an unrooted binary tree is defined more specifically: all internal nodes have degree 3. In turn, a rooted binary tree is such that only the root has degree 2 (all other internal nodes have degree 3).

Given: A positive integer nn (3n100003≤n≤10000).

Return: The number of internal nodes of any unrooted binary tree having nn leaves.

Sample Dataset

4

Sample Output

2

 

 이 문제는 n개의 leaf를 가지고 있는 unrooted binary tree 에서의 internal node의 개수를 구하는 문제이다. 문제 자체는 쉬우나 개념을 알아야 풀 수 있다.

 먼저 degree는 어떤 노드가 다른 노드와 얼마나 연결되어 있느냐를 따지는 단위이다. 3 degree라면 그 노드는 3개의 노드와 연결되어 있는 식이다. binary tree는 각 노드들이 최대 3 degree까지인 트리를 말한다. binary tree의 노드는 1개의 부모 노드, 2개의 자식 노드를 가지고 있는 internal node, 1개의 부모 노드하고만 연결되어 있는 leaf, 2개의 자식 노드하고만 연결되어 있는 root로 나뉠 수 있다. rooted binary tree는 저 3개의 노드 모두 갖고 있는, 즉 root를 가지고 있는 트리이고, unrooted binary tree는 root가 없는, 즉 internal node와 leaf로만 구성 되어있는 트리이다. 

 unrooted binrary tree는 약간 탄화수소를 따지는 감성으로 개수를 추려야 한다. 포화된 탄화수소는 탄소가 4개의 분자결합(3개의 수소,1개의 탄소)을 갖고 있고, 수소는 1개의 분자결합(1개의 탄소)을 갖고 있다. unrooted binary tree는 internal node가 3개의 노드(1개의 internal node,2개의 leaf)와 연결되어 있고, leaf는 1개의 노드(internal node)와 연결되어 있다. 아무튼 그런 감성으로 따져보면 unroooted binary tree는 n개의 leaf를 갖고 있다면 무조건 n-2개의 internal node를 갖고 있다. 

internal node의 개수가 각각 1,2개인 ubt

 

 위 그림처럼 불려나가는 형식이라 생각하면 쉽게 이해할 수 있다. 답은 입력에서 2를 뺀 값을 출력하면 된다.