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

이 글에서는 아래와 같은 문제에 대한 해결 방법을 알아보겠습니다.

문제 정의

하나의 숫자 n이 주어졌을 때, n이 피보나치 수(Fibonacci number)인지 아닌지를 판별하는 프로그램을 작성하는 것이 목표입니다.

피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...처럼 첫 두 항 이후의 모든 항이 바로 앞의 두 항의 합으로 이루어지는 수열입니다. n번째 피보나치 수가 앞선 두 피보나치 수의 합이라는 사실은 누구나 알고 있지만, 사실 피보나치 수에는 점화식 외에도 매우 흥미로운 수학적 성질이 하나 더 존재합니다.

핵심 아이디어: 피보나치 수 판별 정리

어떤 자연수 n이 피보나치 수일 필요충분조건은 다음 두 식 중 하나 이상이 완전제곱수(perfect square)라는 것입니다.

5 × n² + 4
5 × n² − 4

예를 들어 n = 8을 대입해 보면 5 × 64 + 4 = 324 = 18²로 완전제곱수이므로 8은 피보나치 수입니다. 반면 n = 6의 경우 5 × 36 + 4 = 184, 5 × 36 − 4 = 176으로 둘 다 완전제곱수가 아니므로 6은 피보나치 수가 아닙니다.

이 성질을 활용하면 피보나치 수열을 직접 생성하지 않고도 해당 숫자가 피보나치 수인지 빠르게 확인할 수 있습니다.

파이썬 구현 예제

import math

# x가 완전제곱수인지 검사하는 함수
def isPerfectSquare(x):
    s = int(math.sqrt(x))
    return s * s == x

# n이 피보나치 수인지 검사하는 함수
def isFibonacci(n):
    # 5*n*n + 4 또는 5*n*n - 4 중 하나라도 완전제곱수이면 피보나치 수
    return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)

for i in range(1, 11):
    if isFibonacci(i):
        print(i, "-> 피보나치 수입니다")
    else:
        print(i, "-> 피보나치 수가 아닙니다")

실행 결과

1 -> 피보나치 수입니다
2 -> 피보나치 수입니다
3 -> 피보나치 수입니다
4 -> 피보나치 수가 아닙니다
5 -> 피보나치 수입니다
6 -> 피보나치 수가 아닙니다
7 -> 피보나치 수가 아닙니다
8 -> 피보나치 수입니다
9 -> 피보나치 수가 아닙니다
10 -> 피보나치 수가 아닙니다

코드 설명

isPerfectSquare(x): x의 제곱근을 정수로 변환한 뒤 다시 제곱하여 원래 값과 비교함으로써 x가 완전제곱수인지 확인합니다.
isFibonacci(n): 앞서 소개한 수학적 성질을 그대로 구현한 함수로, 5n² + 4와 5n² − 4 중 하나라도 완전제곱수이면 True를 반환합니다.
모든 함수와 변수는 전역 프레임(global frame)에 선언되어 프로그램 전체에서 접근할 수 있습니다.

참고: 매우 큰 숫자를 다룰 때는 부동소수점 연산으로 인한 오차를 피하기 위해 int(math.sqrt(x)) 대신 파이썬 3.8 이상에서 제공하는 math.isqrt(x)를 사용하는 것이 안전합니다.

결론

이번 글에서는 '5n² ± 4가 완전제곱수인가?'라는 수학적 성질을 이용해 주어진 숫자가 피보나치 수인지 판별하는 방법을 살펴보았습니다. 이 방식은 수열을 일일이 계산하지 않고도 상수 시간에 가깝게 판별할 수 있어 매우 효율적입니다.