[java] 피보나치 수열 구현

알고리즘 문제중 빠지지 않고 나오는것이 피보나치 수열 계산이다.

수식은 f(n) = f(n-1) + f(n-2) 으로써 문제 자체가 답인 경우라 재귀함수를 쓴다면 쉽게 구현이 가능하다

public class Fibonacci {

    public static void main(String[] args) throws Exception{
        int result = new Fibonacci().solution(40);
        System.out.println("final result >> " + result);
    }

    public int solution(int n) {
        if(n < 1 || n > 40){
            System.out.println("입력값은 1이상 40 이하여야 합니다.");
        }
        return fib(n);
    }

    private int fib(int n){
        if(n == 0 || n == 1){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
}

 

그런데 이 재귀 방식은 알고리즘 복잡도가 O(2^n/2) 이라 숫자가 커지면 실행속도가 기하급수적으로 증가한다.

예를 들어 n=5 일때는

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

f(2) = f(1) + f(0)

0과 1은 그대로 리턴

 

인데 f(5)를 계산할때 f(3)의 결과를 계산해야 하는데 f(4) 계산할때 또 f(3) 을 또 계산하게 된다.

n이 늘어날수록 중복계산이 많아지게 되어 증손자 그래픽카드를 붙여도 계산을 못하게 된다.

그래서 다른 방법으로 한번 계산한 결과를 캐싱해 놓아 다시 호출하였을때는 이미 구해진 값을 돌려주어 계산을 줄이는 방법을 사용할 수 있으며 해당 알고리즘의 복잡도는 O(n)으로 낮아지게 된다. 이 방법은 동적 계획법(dynamic programming) 이라고 한다.

 

다시 아래 java로 구현한 코드를 보자.

public class CachedFibonacci {

    public static void main(String[] args) throws Exception{
        long result = new CachedFibonacci().solution(92);
        System.out.println("final result >> " + result);
    }

    private Map<Integer, Long> cache = new HashMap<>();
    public long solution(int n) {
        if(n < 1 || n > 92){
            System.out.println("입력값은 1이상 92 이하여야 합니다.");
            return -1;
        }

        // solution 1
        cache.put(0, 0L);
        cache.put(1, 1L);
        return fib(n);
    }

    private long fib(int n){

        if(n <= 1) return n;
        if(cache.containsKey(n)){
            System.out.println("cache hit! > " + n);
            return cache.get(n);
        }

        System.out.println("cache non hit! > " + n);
        long val = fib(n-1) + fib(n-2);

        cache.put(n, val);
        return val;
    }
}

이제 좀 더 위 방법을 개선해 보자. 값을 캐싱하기는 하지만 어쨌든 함수를 여러번 호출하며 호출 스택이 쌓이는건 변하지 않는다. 그래서 발상을 전환하여 낮은 수부터 반복하며 더해가는 방법으로 시도를 한다.

public class LoopFibonacci {
    public static void main(String[] args){
        long result = new LoopFibonacci().solution(92);
        System.out.println("final result >> " + result);
    }

    public long solution(int n) {
        long[] cache = new long[n];
        cache[0] = 0;
        cache[1] = 1;

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

        return cache[n-1] + cache[n-2];
    }
}

낮은값부터 계산하여 올라가기 때문에 호출도 여러번 일어나지 않는다. 해당 알고리즘의 복잡도는 O(n)이다. 이 방법은 우리가 자주 사용하는 반복자를 이용하여서 반복 알고리즘이라고 한다.

 

마지막으로 위 세가지 알고리즘을 다시 한번 확인해 보자

알고리즘	시간 복잡도	특징
재귀 알고리즘	O(2^n/2)	이해하기 쉬움
동적 알고리즘	O(n)	결과값 저장을 위한 메모리 사용
반복 알고리즘	O(n)	결과값 저장을 위한 메모리 사용 복잡한 경우 코드가 난해해짐