주어진 배열이 피보나치 수열을 나타내는지 확인하는 문제를 풀어보겠습니다. 피보나치 수열은 이전의 두 숫자를 더하여 생성되는 수열입니다.

피보나치 수열의 첫 번째와 두 번째 요소는 각각 0과 1입니다. 이를 기반으로 나머지 요소들을 더해 나가면 됩니다.

알고리즘 설명

1. 주어진 배열이 비어있거나 길이가 1 이하인 경우, 무조건 피보나치 수열이 아니므로 False를 반환합니다.
2. 배열의 첫 번째와 두 번째 요소를 각각 0과 1로 설정합니다.
3. 배열의 세 번째 요소부터 순회하면서, 이전 두 요소를 더한 값과 현재 요소가 같은지 확인합니다. 같지 않다면 False를 반환합니다.
4. 순회가 끝난 후에도 False가 반환되지 않았다면, 배열은 피보나치 수열입니다. 따라서 True를 반환합니다.

예시 코드

def is_fibonacci(arr):
    if len(arr) <= 1:
        return False
    
    num1, num2 = 0, 1

    for i in range(2, len(arr)):
        num3 = num1 + num2
        if arr[i] != num3:
            return False
        
        num1 = num2
        num2 = num3
    
    return True

사용 예시

fibonacci_sequence = [0, 1, 1, 2, 3, 5, 8]
print(is_fibonacci(fibonacci_sequence))  # Output: True

non_fibonacci_sequence = [0, 1, 2, 4, 7, 11]
print(is_fibonacci(non_fibonacci_sequence))  # Output: False

위의 예시 코드에서는 is_fibonacci 함수를 정의하고, 주어진 배열이 피보나치 수열인지 확인하는 방법을 구현하였습니다. 두 가지 예시를 통해 함수를 호출하고 결과를 출력해보았습니다.

결론

배열의 요소가 피보나치 수열인지 확인하는 알고리즘을 구현하고 예제 코드를 통해 사용해보았습니다. 이를 활용하여 주어진 배열이 피보나치 수열에 해당하는지 손쉽게 확인할 수 있습니다.

태그: #알고리즘 #피보나치수열