[C++] 백준(BOJ) - 9934 : 완전 이진 트리

01 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 9934 : 완전 이진 트리(링크)

알고리즘

1. 완전 이진 트리
2. 재귀
3. 이분 탐색

풀이

1. 완전 이진 트리의 노드 수는 2^depth - 1 개
2. InOrder 순회를 입력받아 트리를 만드는 문제
3. 이분 탐색을 통해 재귀 함수를 구현한다
   • int mid = (s+e) / 2;
   • s <= e 인 구간 동안 계속해서 구간을 나누어서 재귀 함수를 호출

코드

// BOJ-9934 : 완전 이진 트리
#include<bits/stdc++.h>
using namespace std;

int n;
int a[1030];
vector<int> v[14];

void go(int s, int e, int lv)
{
	if (s > e) return; // 초기 조건
	if (s == e)
	{
		v[lv].push_back(a[s]);
		return;
	}
	int mid = (s + e) / 2; // s <= e 를 기반으로 생각
	v[lv].push_back(a[mid]);
	go(s, mid - 1, lv + 1);
	go(mid + 1, e, lv + 1);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	int _end = (int)pow(2, n) - 1;

	for (int i = 0; i < _end; i++)
	{
		cin >> a[i];
	}

	go(0, _end, 1);

	for (int i = 1; i <= n; i++)
	{
		for (int j : v[i])
		{
			cout << j << ' ';
		}
		cout << "\n";
	}

	return 0;
}

평가

• 이분 탐색 또한 자주 나오는 출제 유형이므로 만드는 꼴과 재귀 함수의 형태를 잘 기억할 수 있도록 한다