피보나치 수열

피보나치 수열이란?

수학에서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

피보나치 수열은 1228년 '피보나치' 라는 수학자가 만들어서 피보나치 수열이라고 한다.

유명한 이유

그런데 왜 이 수열이 그토록 유명한걸까?
첫째 항과 둘째항의 합이 셋째 항인 것이 뭐가 그렇게 중요해서 1000년 넘게 다루는걸까?

1. 황금비
   황금비는 피보나치 수열의 비율은 극한에서 황금비(약 1.618)에 수렴한다.
   연관이 없어보이는 두 수식에서 신기하게도 연관관계가 나오기 때문에 최근까지도 수학자들의 연구대상이 된다.

2. 수학적 특성
   "어떤 피보나치 수를 제곱한 값과 그 이전 및 이후의 피보나치 수를 곱한 값의 차이는 항상 1이 된다"는 신기한 특성을 갖고 있다. 이러한 이유에서도 많은 연구가 이루어지고있다.

• 예시

fibonacci(3) - (fibonacci(2) * fibonacci(4)) = 1
-> 2^2 - (1*3) 
-> 4 - 3 = 1

작동방식 (반복문 - 메모이제이션 자동적용)

// 반복문 사용
public class Main
{
    public static void main(String[] args) {
        
        int[] arr = new int[100];
        
        // An = An-1 + An-2; n>=3
        // a1 = 1, a2 = 1 
        arr[1] = 1;
        arr[2] = 1;
        
        for (int i=3; i<100 ; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        } 
        for (int i=1; i<=10 ; i++) {
            System.out.println(arr[i] + " ");
        } 

반복문을 사용하여 피보나치 수열을 구할 땐, 자동으로 메모이제이션이 적용된다.
왜냐하면 만약 fibonacci(4)를 구한다면, fibonacci(0) 부터 순차적으로 arr에 저장해가면서 계산하기 때문이다.

arr[3]=2이고, 이 값을 arr에 저장해놨다.
arr[4]를 구하려면 arr[3]이 필요한데, 이는 arr에 저장되어 있기 때문에 메모이제이션이 자동으로 이루어져있음을 알 수 있다.

작동방식(재귀함수 - 메모이제이션X)

// 2. 재귀함수 사용
public class Main {  
    public static void main(String[] args) {
        int n = 8;
        
        System.out.println(fibonacci(n));
    }
    
    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        } 
        return (fibonacci(n-1) + fibonacci(n-2));
    }
}

재귀함수로도 피보나치 수열을 구현할 수 있다.
하지만 위 방법은 "실행시간이 아주 오래걸린다"는 치명적인 단점이 있다.
만약 n이 아주 큰 수라면, 몇시간이 걸릴 수도 있을 것이다.
원인은 값을 저장하지 않기 때문이다.

fibonacci(5)를 예를 들어 알아보자.

fibonacci(5)를 실행하면 n이 1 또는 0일때까지 fibonacci()를 계속 호출한다.
첫번째 단계에서 fibonacci(4) 를 계산한다.
두번째 단계에서 fibonacci(3)와 fibonacci(2)를 더한다.
세번째 단계에서 fibonacci(2)와 fibonacci(1)를 더한다.
네번째 단계에서 fibonacci(1)와 fibonacci(0)를 더한다.

이 과정을 거치면서 fibonacci(2)=1, fibonacci(1)=1이라는 것을 알아냈다.
하지만 이 값을 저장하지 않았기 때문에
첫번째 단계의 fibonacci(3) 을 구할 때 또다시 fibonacci(2), fibonacci(1)을 계산하기 때문에 시간이 많이 걸리는 것이다.

메모이제이션

동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다. 동적 계획법의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이다. 메모이제이션은 아무래도 학술적인 용어라 실제 현장에서는 캐싱(caching)이라는 단어를 더 많이 사용한다.

위 그림은 메모이제이션을 사용하지 않은 경우다. 맨 왼쪽에 있는 fib(3)을 구하면서 fib(3), fib(2), fib(1), fib(0)을 모두 구했지만, 값을 저장하지 않았다.
따라서 fib(2)를 구하기 위해 또다시 계산을 했고, 마찬가지로 맨 오른쪽의 fib(3)을 구할 때에도 계산을 수행했다.

만약 맨 왼쪽의 fib(3)을 계산하는 과정에서 fib(3), fib(2), fib(1), fib(0)을 저장했다면 위처럼 저장된 값을 사용하여 짧은 시간이 걸렸을 것이다.

구현코드

public class Main {
    static int n = 8; // 예시로 8을 사용
    static int[] fibonacciCache = new int[n + 1];
    
    
    public static void main(String[] args) {
        System.out.println(fibonacci(n));
    }
    
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        // 이미 계산된 값이 캐시에 있는지 확인
        if (fibonacciCache[n] != 0) {
            return fibonacciCache[n];
        }
        // 캐시에 없다면 계산 후 캐시에 저장
        fibonacciCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return fibonacciCache[n];
    }
}

피보나치 수열 5

import java.io.*;

class Main {
    private static long[] fibonacciCache;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        /**
         * fibonacciCache = new long[n+1]; 에 n이 아닌 n+1를 하는 이유는 아래와 같다.
         * 만약 fibonacci(3)을 구하고자 할 때, fibonacciCache에 [0,1,1,2] 가 저장될 것이다.
         * 이 때, fibonacciCache의 size는 !!4!! 이므로 n+1을 해주어야만 한다.
         */
        fibonacciCache = new long[n + 1];
        long result = fibonacci(n);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(result));

        bw.flush();
        bw.close();
        br.close();
    }

    static long fibonacci(int n) {
        // base case
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        /** 또는 아래로도 작성할 수 있다. 
        if (n <= 0) {
            return n;
        }
         */
        
        // recursive case
        if (fibonacciCache[n] != 0) {
            // fibonacciCache에 값이 있다면, 거기에서 꺼내서 반환하라
            return fibonacciCache[n];
        }
        
        // fibonacciCache에 값이 없다면, 계산 후 저장하라.
        fibonacciCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return fibonacciCache[n];
    }
}

코드는 동일하다.

• 시간복잡도
  만약 메모이제이션을 사용하지 않았다면, 시간복잡도는 O(2^n)지만, 사용하면 O(n)으로 변경된다.
• 문제풀이의 핵심은..??
  • 재귀 함수 사용할 때, Memoization을 무조건 사용하기!
  • 반복문은 자동으로 Memoization이 적용된다.
• 어려웠던 점
  -> fibonacci(n) + fibonacci(m)의 작동 순서는 첫번째 요소를 구한 후, 두번째 요소를 구하는 방식으로 진행된다. 컴퓨터가 동시에 두 fibonacci()에 대한 작업을 진행하지는 않는다.