피보나치 수열(Fibonacci Sequence)

이번에는 피보나치 수열을 구현해보자.

 

피보나치는 아래와 같이 n번 째 값은 n-1번째 n-2번 째 값의 합이다.

 

피보나치 수열

1. 먼저 함수에 표현된 대로 코드를 구성해 보자.

 함수대로 표현하기 위해서는 재귀함수 방식을 활용해야 한다.

즉 int n에 해당하는 값을 구하기 위해  "n-2"번 째 값과 "n-1"번 째 값을 추가로 계산을 해줘야 한다.

package fibonacci;

public class FibonacciPractice {

    public int fibonacciRecur(int n){

        if(n == 0) return 0;
        if(n == 1) return 1;

        return fibonacciRecur(n-2) + fibonacciRecur(n-1);

    }

    public static void main(String[] args) {

        FibonacciPractice fibonacciPractice = new FibonacciPractice();

        int n = 3;
        int result = fibonacciPractice.fibonacciRecur(n);

        System.out.println("F("+n+") = " + result);
    }
}

- 실행 결과

F(3) = 2

이처럼 재귀함수 방식은 코드가 함수와 바로 매칭이 되기 때문에 가장 직관적이다. 하지만 코드에서 볼 수 있듯이

이전 2개 항들에 대해 추가로 계산이 필요하다. 

 

이해하기 쉽게 그림으로 보자.

즉, F(n)을 계산하기 위한 method에서 F(n-2), F(n-1)계산기 필요하고, 다시 F(n-2)를 계산하기 위해 F(n-4), F(n-3)을 계산.....한마디로 n에 따라 계산 횟수가 기하급수적으로 늘어난다!.

 

즉, Fibonacci수열을 재귀함수 형식을 적용하면 O(n^2)이다.

 

 

2. for문을 돌리자.

반목문을 돌면서 n-1항, n-2항에 대한 값을 계속 업데이트 하여 F(n)에 해당하는 값을 계산한다.

for문으로 구현한 경우 계산 횟수는 n에 비례한다. 따라서 O(n)이다.

package fibonacci;

public class FibonacciPractice {

    public int fibonacciFor(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;

        int prepre = 0;
        int pre = 1;
        int Fn = 0;
      
        for(int i=2;i<=n;i++){

            Fn = prepre + pre;
            prepre = pre;
            pre = Fn;


        }
        return Fn;
    }

    public static void main(String[] args) {

        FibonacciPractice fibonacciPractice = new FibonacciPractice();

        int n = 5;
        int result = fibonacciPractice.fibonacciRecur(n);

        System.out.println("재귀 : F("+n+") = " + result);

        int resultFor = fibonacciPractice.fibonacciFor(n);
        System.out.println("for : F("+n+") = " + resultFor);
    }
}

-실행결과

재귀 : F(5) = 5
for : F(5) = 5

 

3. 메모이제이션(memoization) :  

메모이제이션이란? 반복계산을 할 때 각 단계에서 계산된 결과값을 저장하고, 호출하여 반복적인 계산을 줄일 수 있다. 

따라서 실행 속도를 빠르게 할 수 있다. 

 

    public int fibonacciMemo(int n){
        fibonacciArray = new int[50];
        fibonacciArray[0] = 0;
        fibonacciArray[1]=1;

        if(n==0) return fibonacciArray[0];
        if(n==1) return fibonacciArray[1];

        for(int i=2;i<=n;i++){

            fibonacciArray[i] = fibonacciArray[i-2]+fibonacciArray[i-1];
        }

        return fibonacciArray[n];

    }

4. 전체 코드

package fibonacci;

import java.sql.Time;

public class FibonacciPractice {

    int[] fibonacciArray;
    int countRecur= 0;
    int countFor= 0;
    int countMem= 0;
    public int fibonacciRecur(int n){
        countRecur++;
        if(n == 0) return 0;
        if(n == 1) return 1;

        return fibonacciRecur(n-2) + fibonacciRecur(n-1);

    }

    public int fibonacciFor(int n){
        long start = (long) System.currentTimeMillis();
        if(n == 0) return 0;
        if(n == 1) return 1;

        int prepre = 0;
        int pre = 1;
        int Fn = 0;

        for(int i=2;i<=n;i++){
            countFor++;
            Fn = prepre + pre;
            prepre = pre;
            pre = Fn;


        }

        return Fn;
    }

    public int fibonacciMemo(int n){


        fibonacciArray = new int[50];
        fibonacciArray[0] = 0;
        fibonacciArray[1]=1;

        if(n==0) return fibonacciArray[0];
        if(n==1) return fibonacciArray[1];


        for(int i=2;i<=n;i++){
            countMem++;
            fibonacciArray[i] = fibonacciArray[i-2]+fibonacciArray[i-1];
        }


        return fibonacciArray[n];

    }

    public static void main(String[] args) {

        FibonacciPractice fibonacciPractice = new FibonacciPractice();

        int n = 15;
        int result = fibonacciPractice.fibonacciRecur(n);


        System.out.println("재귀 : F("+n+") = " + result);
        System.out.println("count : " + fibonacciPractice.countRecur);
        System.out.println("-----------------------------------------");

        int resultFor = fibonacciPractice.fibonacciFor(n);
        System.out.println("for : F("+n+") = " + resultFor);
        System.out.println("count : " + fibonacciPractice.countFor);
        System.out.println("-----------------------------------------");


        int resultMemo = fibonacciPractice.fibonacciMemo(n);
        System.out.println("메모이제이션 : F("+n+") = " + resultMemo);
        System.out.println("count : " + fibonacciPractice.countMem);
        System.out.println("-----------------------------------------");
    }
}

- n=15

재귀 : F(15) = 610
count : 1973
-----------------------------------------
for : F(15) = 610
count : 14
-----------------------------------------
메모이제이션 : F(15) = 610
count : 14
-----------------------------------------