C++에서 X와의 합이 피보나치 수가 되는 노드 개수 구하기

문제 개요

각 노드에 숫자 형태의 가중치가 부여된 이진 트리가 주어졌을 때, 노드의 가중치에 X(temp)를 더한 값이 피보나치 수가 되는 노드의 개수를 구하는 것이 이 글의 목표입니다.

피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13…과 같이 n번째 항이 (n−1)번째 항과 (n−2)번째 항의 합으로 정의되는 수열입니다. 예를 들어 어떤 노드의 가중치가 12이고 temp가 1이라면 12+1=13은 피보나치 수이므로 이 노드는 개수에 포함됩니다.

예제 1

입력

temp = 1. 값을 입력하면 아래와 같은 트리가 생성됩니다.

출력

X와의 합이 피보나치 수인 노드의 개수: 3

설명

트리의 각 노드와 노드별 가중치가 주어져 있으며, 각 노드마다 temp + 가중치가 피보나치 수인지 하나씩 검사합니다.

표에서 피보나치 수에 해당하는 경우는 3개이므로 최종 결과값은 3이 됩니다.

예제 2

입력

temp = 3. 값을 입력하면 아래와 같은 트리가 생성됩니다.

출력

X와의 합이 피보나치 수인 노드의 개수: 3

설명

마찬가지로 각 노드의 가중치에 temp를 더한 값이 피보나치 수인지 확인합니다.

접근 방식

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

트리를 그래프로 보고 DFS(깊이 우선 탐색)로 순회하면서, 각 노드의 가중치와 temp의 합이 피보나치 수가 되는지 확인합니다. 이를 위해 두 개의 벡터 Node_Weight(100)와 edge_graph[100]를 사용합니다.

• Node_Weight[]를 노드들의 가중치 값으로 초기화합니다.
• vector edge_graph를 이용해 트리를 생성합니다.
• 전역 변수 Fibonacci를 선언하고 0으로 초기화합니다. 전역 변수 temp도 함께 선언합니다.
• 함수 check_square(long double val)는 정수를 받아 val이 완전 제곱수이면 true를 반환합니다.
• val_1 = sqrt(val)로 제곱근을 구합니다.
• if(val_1 − floor(val_1) == 0)이 참이면 val은 완전 제곱수이므로 true를 반환합니다.
• 그렇지 않으면 false를 반환합니다.
• 함수 check_Fibonacci(int num)는 num이 피보나치 수이면 true를 반환합니다. 이때 “5×num²+4 또는 5×num²−4가 완전 제곱수이면 num은 피보나치 수다”라는 잘 알려진 수학적 성질을 활용합니다.
• fib를 5 * num * num으로 초기화합니다.
• check_square((fib + 4)) || check_square((fib − 4))가 참이면 true를 반환합니다.
• 그렇지 않으면 false를 반환합니다.
• 함수 Fibonacci_number(int node, int root)는 X와의 합이 피보나치 수인 노드의 개수를 계산합니다.
• if(check_Fibonacci(Node_Weight[node] + temp))가 참이면 Fibonacci를 1 증가시킵니다.
• for 루프를 사용해 vector edge_graph[node]에 연결된 트리를 순회합니다.
• 벡터의 다음 노드에 대해 Fibonacci_number(it, node)를 재귀적으로 호출합니다.
• 모든 탐색이 끝나면 Fibonacci에는 temp와의 합이 피보나치 수가 되는 가중치를 가진 노드의 개수가 저장됩니다.

코드 예제

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int Fibonacci = 0, temp;
bool check_square(long double val){
    long double val_1 = sqrt(val);
    if(val_1 − floor(val_1) == 0){
        return true;
    }
    return false;
}
bool check_Fibonacci(int num){
    int fib = 5 * num * num;
    if(check_square((fib + 4)) || check_square((fib − 4))){
        return true;
    }
    return false;
}
void Fibonacci_number(int node, int root){
    if(check_Fibonacci(Node_Weight[node] + temp)){
        Fibonacci++;
    }
    for (int it : edge_graph[node]){
        if(it == root){
            continue;
        }
        Fibonacci_number(it, node);
    }
}
int main(){
    //노드의 가중치
    Node_Weight[2] = 6;
    Node_Weight[1] = 4;
    Node_Weight[4] = 23;
    Node_Weight[3] = 5;
    Node_Weight[8] = 161;
    Node_Weight[9] = 434;
    //그래프 간선 생성
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    temp = 3;
    Fibonacci_number(2, 2);
    cout<<"X와의 합이 피보나치 수인 노드의 개수: "<<Fibonacci;
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

X와의 합이 피보나치 수인 노드의 개수: 1