Coding Ha

void

연습문제 2-5(5) min heap

문제 설명 이진 힙은 항상 부모 노드가 가지는 값이 자식 노드가 가지는 값보다 크거나 (max heap) 혹은 작거나 같다는 (min heap) 조건을 만족하는 완전 이진 트리(Complete binary tree) 형태의 자료구조이비다. 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽에서부터 순서대로 나열되는 이진 트리를 말합니다. 이러한 이진 힙은 보통 배열을 통해서 구현하게 됩니다. 배열의 0번 인덱스는 사용하지 않고, 배열의 1번 인덱스에 루트 노드의 값을 저장합니다. 현재 노드의 인덱스가 i일 때, i*2 인덱스에 왼쪽 자식 노드, i*2+1 인덱스에 오른쪽 자식 노드를 저장합니다. 예를 들어 {0, 5, 10, 15}는 루트 노..

연습문제 2-5(4) 포화 이진 트리 노드 개수

문제 설명 포화 이진 트리(Perfect binary tree)란, 리프 노드를 제외한 모든 노드가 2개의 자식 노드를 가지는 트리를 말합니다. 높이가 n인 포화 이진 트리의 전체 노드 수를 구하려고 합니다. 높이 n이 주어질 때, 트리의 모든 노드 개수를 출력하는 프로그램을 구현하세요. 결괏값이 매우 클 수 있으니, 결과를 1,000,000,007로 나눈 나머지 값을 반환해 주세요. · 참고 : 포화 이진 트리의 구조(출처 : https://iq.opengenus.org/perfect-binary-tree/) 입력 형식 · n : 포화 이진 트리의 높이(정수) 출력 형식 · 높이가 n인 포화 이진 트리의 노드의 개수를 정수로 반환 제약 사항 · 1