[JAVA] 피보나치(fibonacci) 문제

면접 단골문제인 피보나치(fibonacci) 구현

1에서 n까지의 피보나치 수열을 반환하는 메서드를 작성하라.

---

public static List<Integer> fibonacci(int n){
        if(n<0){
            throw new IllegalArgumentException("n must be less than 0");
        }
        if(n == 0) {
            return new ArrayList<>();
        }
        if(n == 1) {
            return Arrays.asList(0);
        }
        if(n == 2) {
            return Arrays.asList(0, 1);
        }
        
        final List<Integer> result = new ArrayList<>();
        result.add(0);
        result.add(1);
        n = n-2;
        /*
        for(int i=0; i<n; i++) {
            int next = result.get(i) + result.get(i+1);
            result.add(next);
        }*/
        
        while(n>0) {
            int a = result.get(result.size()-2);
            int b = result.get(result.size()-1);
            result.add(a+b);
            n = n-1;
        }
        
        return result;
    }

피보나치 수열의 n번째 값을 반환하는 메서드를 작성하라.

---

위의 방법을 사용하여 n 마지막 값을 반환하면 문제의 답을 얻을 수 있으나, 리스트틀 만드는데 메모리를 많이 소모한다는 단점이 있다. 한 가지 대안으로 재귀적 방법을 사용하는 법이 있다. 

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);

Fibonacci(0) = 0;

Fibonacci(1) = 1;

public static int fibN(int n) {
        if(n < 0)
            throw new IllegalArgumentException("n must not be less than zero");
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        return fibN(n-1) + fibN(n-2);
    }

코드는 이쁘지만 매우 비효율 적이다. 40 번째 값을 계산한다고 하였을 때, Fibonacci(38) + Fibonacci(39) 를 더해서 만들어진다. Fibonacci(39)는 Fibonacci(37) + Fibonacci(38)을 더해서 만들어 진다. 두 경우 모두 Fibonacci(38)을 사용해서 연산해야 하는데, 이는 실행할 때마다 메서드를 불러와야 하는악순환의 연속이다.

이 대응법으로 Map 자료형으로 Cache한 값을 사용할 수 있다.(memoization)

private Map<Integer, Integer> fibCache = new HashMap<>();
 
public int cachedFibN(int n) {
        if(n < 0)
            throw new IllegalArgumentException("n must not be less than zero");
        fibCache.put(0, 0);
        fibCache.put(1, 1);
        return recursiveCachedFibN(n);
    }
    
    private int recursiveCachedFibN(int n) {
        if(fibCache.containsKey(n))
            return fibCache.get(n);
        
        int value = recursiveCachedFibN(n-1) + recursiveCachedFibN(n-2);
        fibCache.put(n, value);
        return value;
    }

Map에 캐쉬된 값을 넣어서 캐쉬된 값을 이용하여 n 번째 피보나치 숫자를 구하는 방법이다.

문득 예전에 구현한 동적프로그래밍 기법이 생각나서

동적프로그래밍기법, memoization 기법, 재귀함수의 성능을 알아보는 테스트 코드를 작성해보았다. 

@Test
    public void largeFib() {
        Fibonacci fb = new Fibonacci();
        final long nonCachedStart = System.nanoTime();
        assertEquals(1134903170, fb.fibN(45));
        final long nonCachedFinish = System.nanoTime();
        assertEquals(1134903170, fb.cachedFibN(45));
        final long cachedFinish = System.nanoTime();
        assertEquals(1134903170, fb.dynamicFibonacci(45));
        final long dynamicFinish = System.nanoTime();
        
        System.out.printf("Non cached time : %d nanoseconds%n", nonCachedFinish - nonCachedStart);
        System.out.printf("cached time : %d nanoseconds%n", cachedFinish - nonCachedFinish);
        System.out.printf("dynamic time : %d nanoseconds%n", dynamicFinish - cachedFinish);
        
    }

테스트 코드는 위와 같으며 45번째 피보나치 수열을 구하는 코드이다.

결과는

Non cached time : 5307780091 nanoseconds

cached time : 157783 nanoseconds

dynamic time : 5428 nanoseconds

이렇게 나왔다.

뭐 컴퓨터 성능에 따라서 숫자가 달라질 수 있지만, 중요한것은 재귀함수는 상당히 시간이 오래걸린다는 것을 알수 있다.

동적 프로그래밍이 역시 가장 빠르다...