[Java] 피보나치 수열 구현

▤ 목차

1. 피보나치 수열이란

피보나치 수열(Fibonacci numbers) 이란?

• ‘이전 두 항의 합이 다음 항이 되는 수열’을 의미
• 즉, 첫째 항과 둘째 항이 1이고 이후 모든 항은 모든 항은 바로 앞 두항의 합으로 이루어지는 수열
• 피보나치 수열의 예로는 [1, 1, 2, 3, 5, 8, 13, 21, 34,...]과 같은 형태로 구성

2. 반복문으로 구현

public static int Fibonacci(int n) {
    int answer = 0;
    if (n <= 1) return n; //값이 1인 경우 해당 값을 반환

    int pprev = 1; // 첫번째값
    int prev = 2; // 두번째값

    //세번째 값부터 n까지 반복
    for (int i = 3; i <= n; i++) {
       answer = prev + pprev; // 세번째값 = 첫번째값 + 두번째값 
       pprev = prev;
       prev = answer; 
    }
    return answer;
}

3. 재귀함수로 구현

public static int recursiveFibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
        }
    }

단 재귀 알고리즘으로 구현하는 경우, 구하려고 하는 숫자가 커질수록 메모리 속도가 현저하게 떨어진다는 단점이 있다.

불필요한 중복 값을 방지하기 위해 계산한 값을 저장해 두는 메모라이제이션 기법을 사용하여 구현해야 한다.

 

메모라이제이션 기법 사용(추천)

static long[] memo;
public static long recursiveFibonacci(int n) {
        if (n <= 1)
            return n;
        else if (memo[n] != 0)
            return memo[n];
        else
            return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
 
    }

4. 동적계획법(DP)으로 구현(추천)

public static int dynamicFibonacci(int n) {
        if (n <= 1) { //값이 1인 경우 해당 값을 반환
            return n;
        }

        // 첫번째와 두번째 배열에 값을 지정
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        // 3번째부터 n까지 반복
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

시간 복잡도는 O(n)으로 효율적인 구현 방법이다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.