이 글에서는 주어진 숫자가 피보나치 수(Fibonacci Number)인지 판별하는 문제를 파이썬 코드로 해결하는 방법을 알아봅니다.
문제 정의
하나의 숫자 n이 주어졌을 때, n이 피보나치 수인지 아닌지를 판별하는 프로그램을 작성하는 것이 목표입니다.
피보나치 수열은 각 항이 바로 앞의 두 항의 합으로 이루어지는 수열로 잘 알려져 있습니다. 즉, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...와 같은 형태로 진행됩니다. 하지만 흥미롭게도 이 점화식 외에도 피보나치 수만이 가지는 독특한 수학적 성질이 존재합니다.
핵심 아이디어: 피보나치 수의 수학적 성질
어떤 숫자 n이 피보나치 수일 필요충분조건은 다음과 같습니다.
(5 × n² + 4) 또는 (5 × n² − 4) 중 하나 이상이 완전제곱수(perfect square)일 것
여기서 완전제곱수란 어떤 정수의 제곱으로 표현할 수 있는 수를 의미합니다. 예를 들어 0, 1, 4, 9, 16, 25 등이 해당됩니다. 이 성질을 활용하면 실제로 피보나치 수열을 일일이 생성하지 않고도 O(1)에 가까운 효율적인 방식으로 판별할 수 있습니다.
이제 파이썬 스크립트 구현 과정을 살펴보겠습니다.
구현 예제
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) == True):
print(i, "is a Fibonacci Number")
else:
print(i, "is a not Fibonacci Number")
실행 결과
1 is a Fibonacci Number 2 is a Fibonacci Number 3 is a Fibonacci Number 4 is a not Fibonacci Number 5 is a Fibonacci Number 6 is a not Fibonacci Number 7 is a not Fibonacci Number 8 is a Fibonacci Number 9 is a not Fibonacci Number 10 is a not Fibonacci Number
실행 결과를 보면 1, 2, 3, 5, 8은 피보나치 수로 올바르게 판별되었고, 4, 6, 7, 9, 10은 피보나치 수가 아닌 것으로 정확히 걸러진 것을 확인할 수 있습니다.
코드 동작 원리 상세 설명
1. isPerfectSquare 함수
math.sqrt()로 입력값의 제곱근을 구한 뒤 정수형으로 변환합니다. 그 후 그 값을 다시 제곱하여 원래 값과 비교함으로써 완전제곱수 여부를 검사합니다. 부동소수점 오차를 고려해 int()로 내림 처리한 뒤 재검증하는 방식이라 안정적입니다.
2. isFibonacci 함수
앞서 소개한 수학적 성질을 그대로 코드로 옮긴 부분입니다. 5n² + 4 또는 5n² − 4 중 하나라도 완전제곱수라면 True를 반환하여 해당 숫자가 피보나치 수임을 알려줍니다.
3. 전역 프레임에서의 실행
모든 함수와 변수는 전역 프레임(global frame)에 선언되어 실행되며, 반복문을 통해 1부터 10까지의 숫자를 차례대로 검사하고 결과를 출력합니다.
마무리
이번 글에서는 단순히 피보나치 수열을 생성해 비교하는 대신, 완전제곱수를 활용한 수학적 성질을 이용해 주어진 숫자가 피보나치 수인지 효율적으로 판별하는 파이썬 구현 방법을 학습했습니다. 이 기법은 큰 수에 대해서도 빠르게 동작하므로 실무에서 유용하게 활용할 수 있습니다.