파이썬으로 주어진 숫자가 피보나치 수인지 확인하는 방법

숫자 n이 주어졌을 때, 이 숫자가 피보나치 수열에 포함되어 있는지 확인해야 합니다. 피보나치 수열은 f(0) = 0, f(1) = 1이며, i가 2부터 n까지 각 항이 f(i) = f(i-1) + f(i-2) 공식을 따르는 수열입니다.

예를 들어 입력값이 n = 13이라면 출력은 True가 됩니다. 피보나치 수열의 항들은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34와 같이 나열되므로 13이 수열에 존재하기 때문입니다.

해결 접근 방식

이 문제는 황금비(Golden Ratio)의 성질을 활용하면 효율적으로 해결할 수 있습니다. 황금비 φ는 약 1.6180339887의 값으로, 인접한 두 피보나치 수의 비가 이 값에 수렴한다는 특징이 있습니다.

구체적인 단계는 다음과 같습니다.

• 황금비 phi := 0.5 + 0.5 * √5 를 계산합니다.
• a := phi * n 을 구합니다.
• n이 0이거나 a가 정수에 충분히 가깝다면 True를 반환합니다.

여기서 부동소수점 연산 오차를 고려하여, a를 반올림한 값과 a의 차이가 1/n보다 작은지로 판단합니다. 이는 부동소수점 정밀도 문제로 인한 오판을 방지하는 안전장치입니다.

예제 코드

아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.

from math import sqrt

def solve(n):
    phi = 0.5 + 0.5 * 5.0**0.5
    a = phi * n
    return n == 0 or abs(round(a) - a) < 1.0 / n

n = 13
print(solve(n))

입력

13

출력

True

복잡도 분석

이 방법의 시간 복잡도는 O(1)입니다. 수열을 처음부터 하나씩 생성하며 비교하는 방식(O(n))과 달리, 황금비를 이용한 수학적 판별법은 입력 크기와 무관하게 상수 시간 안에 결과를 얻을 수 있다는 것이 가장 큰 장점입니다.