-
BOJ 9934 완전 이진 트리Problem_Solving 2020. 2. 2. 17:41
#문제 설명
주어진 조건과 노드의 순서를 보고 완전 이진 트리를 구하는 문제
- 주어진 조건
1) 루트에서 시작
2) 왼쪽 노드를 방문하지 않았다면 왼쪽 노드 방문
3) 왼쪽노드를 가지고 있지 않았을 경우와 왼쪽 노드를 이미 방문한 경우 종이에 노드번호를 적는다.
4) 현재 노드를 방문한 상태이고, 오른쪽 노드를 가지고 있는경우 오른쪽 노드 방문
5) 왼쪽, 오른쪽 노드를 모두 방문했다면 부모 노드로 이동
#문제 풀이
데이터를 보면 가장 작은 단위의 서브 트리가 왼쪽 자식 부모 오른쪽 자식으로 구성 되어 있는것을 알 수 있다.
수열을 반으로 나눈 인덱스가 루트이고 반으로 나눈 인덱스 기준으로 왼쪽은 왼쪽 자식 오른 쪽은 오른 쪽 자식이다
이규칙을 이용하여 재귀적으로 문제를 푼다.
추가적으로 완전 이진 트리의 특징을 보면
노드 개수는 2^h - 1 개의 노드를 가질 수 있다(h는 트리의 높이)
해당 문제에서 K는 트리의 높이로 보아도 된다.'Problem_Solving' 카테고리의 다른 글
BOJ 2357 최솟값과 최댓값 (0) 2020.02.01 Codeforce #521 Div3 D. Cutting Out (0) 2018.11.18 Codeforce #521 Div3 E. Thematic Contests (0) 2018.11.18 Array Manipulation (0) 2018.11.11 Codeforce #515 Binary Numbers AND Sum (0) 2018.10.28 댓글