피보나치 수열 구현 - 1단계

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

# 일부코드에서 Scanner 코드를 제거 하겠습니다.#

피보나치 수 부터 설명을 하자면

첫번째 항이 0 부터 시작할 경우 첫번째 항은 0, 두번째 항은 1부터 시작하여, 다음 항은 직전 항과 직전 항의 직전 항의 합으로 이루어진 수열을 의미한다.

즉, 피보나치 수 𝐹𝑛 은 다음과 같이 정의할 수 있다.

𝐹𝑛 = 𝐹𝑛-1 + 𝐹𝑛-2 ( 𝑛 ∈ {2, 3, 4, … } )

그리고 위 점화식을 이용하여 구해본다면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

풀이

for문을 사용

public class Fibonacci {
    public static void main(String[] args) {
    
        int n = 10; // 피보나치 수열의 길이

        // 초기값 설정
        int num1 = 0;
        int num2 = 1;
		
        // 피보나치 수열: 
        System.out.print("피보나치 수열: ");

        // for문을 사용하여 피보나치 수열 출력
        for (int i = 1; i <= n; i++) {
        	// 0 1 1 2 3 5 8 13 21 34
            System.out.print(num1 + " ");
            int sum = num1 + num2;

            num1 = num2;
            num2 = sum;
        }
    }
}

for 문을 사용해서 위의 리듬을 간단히 구현 할 수 있다.

재귀함수 사용

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();

        System.out.println(fibonacci(a));
    }

    static int fibonacci(int N) {
        if (N == 0) return 0;

        if (N == 1) return 1;

        return fibonacci(N - 1) + fibonacci( N - 2);
    }
}

위와 같이 재귀함수를 사용해서 구현도 가능하다.

간단한 알고리즘 구현이지만 찾아보니 가끔 실무에서 응용하는 사례도 있다고 한다.

• 암호화: 피보나치 수열의 원리를 기반으로 하는 암호화 알고리즘을 개발할 수 있습니다. 예를 들어, 각 피보나치 수열의 항을 이진수로 변환하고, 변환된 이진수 값을 사용하여 데이터를 암호화하거나 복호화하는 알고리즘을 구현할 수 있습니다.

• 자원 할당: 피보나치 수열은 자원 할당과 관련된 문제를 해결하는 데에도 사용될 수 있습니다. 예를 들어, 피보나치 수열을 사용하여 시간 복잡도가 O(1)인 자원 할당 알고리즘을 구현할 수 있습니다.

• 금융 분석: 피보나치 수열은 금융 분석에도 활용될 수 있습니다. 예를 들어, 주식 시장에서의 가격 변동이나 수익률을 예측하는 데에 피보나치 수열의 원리를 적용할 수 있습니다.

• 자연 현상 모델링: 피보나치 수열은 자연 현상 모델링에도 사용될 수 있습니다. 예를 들어, 꽃잎의 배열이나 나선형 구조 등에서 피보나치 수열이 관찰되는 경우가 있습니다. 이러한 현상을 수학적으로 모델링하고 예측하는 데에 피보나치 수열을 활용할 수 있습니다.

• 동적 프로그래밍: 피보나치 수열은 동적 프로그래밍의 대표적인 예시로 활용됩니다. 동적 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하는 방법을 말하며, 피보나치 수열은 이를 이해하고 구현하는 데에 좋은 예시로 활용될 수 있습니다.

이러한 응용 분야 외에도 피보나치 수열은 수학, 알고리즘, 컴퓨터 과학 등 다양한 분야에서 활용되고 있다고 합니다.