설명

피보나치 수열을 재귀로 푸십시오.

코드

public class Fibonacci {
    public static void main(String[] args) {
        int dfs = DFS(7);
        System.out.println("dfs = " + dfs);

        int n= 45;
        fibo = new int[n+1]; //0번째 배열은 사용하지 않을 것이기 때문에 n+1
        DFS3(n);
        for(int i=1; i<=n; i++) System.out.print(fibo[i] + " ");

        System.out.println();

        int fibonacci = fibonacci(5);
        System.out.println("fibonacci = " + fibonacci);
    }

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

    //만약 코딩 인터뷰에서 fibo의 내용을 출력해야할 경우 효율적인 코드로 짜는 방법
    static int[] fibo;
    public static int DFS2(int n){
        if(n==1) return fibo[1] = 1;
        else if(n==2) return fibo[2] = 1;
        else return fibo[n] = DFS2(n-2) + DFS2(n-1);
    }

    //메모이제이션을 활용하면 더 빨리 결과를 낼수 있다.
    public static int DFS3(int n){
        if(fibo[n] != 0) return fibo[n];
        if(n==1) return fibo[1] = 1;
        else if(n==2) return fibo[2] = 1;
        else return fibo[n] = DFS3(n-2) + DFS3(n-1);
    }

    //반복문으로 fibonacci 풀이
    public static int fibonacci(int n){
        if(n < 2) return 1;
        int result = 0;
        int n1 = 0;
        int n2 = 1;

        for(int i=2; i<=n; i++){
            result = n1 + n2;
            n1 = n2;
            n2 = result;
        }
        return result;
    }
}

학교에서 재귀 함수를 배우기 전에 한번은 거쳐가는 피보나치 수열을 다시 풀어보았다. 물론 재귀로 피보나치를 풀어내는 방법보다 반복문을 사용하여 풀이하는게 효율성이 훨씬 좋다. 그 이유는 재귀적 피보나치는 스택에 프레임을 엄청 많이 사용하게 되는데 10을 입력해서 값을 반환 받으려고 할때 재귀로 호출하는 수 만큼 프레임을 만들어내기 때문이다. 이에 반면 반복문은 하나의 메서드에서 반복을 통해서 값을 반환하기 때문에 하나의 프레임만 사용할 수 있어 재귀보다 반복문이 효율성이 더 좋다.

하지만 이렇게 조건적으로 재귀를 통해 무조건 피보나치를 풀어야하는 상황에서는 좀 더 좋은 효율성 높은 코드를 생산하기 위해 위 코드와 같이 점진적으로 발전해 나가는 코드를 작성해보았다.

DFS
첫번째 DFS는 우리가 흔히 배우고 알고 있는 피보나치 재귀적 풀이 방식이다. 여기서 n의 값이 30만 넘어가도 엄청 느리게 출력되는 것을 알 수 있다.

DFS2
두번째 DFS는 배열을 추가하여 배열을 출력하는 방법인데. 위의 코드가 DFS(1) ~ DFS(n)을 출력할때 하나씩 DFS(1) 출력 -> DFS(2) 출력 -> DFS(3) 출력 -> DFS(n) 출력 의 방식이였다면 DFS2(n)을 입력받아 값들을 배열에 저장해두고 배열 자체를 출력하는 방식으로 변경된 것이다. 이 방법은 첫번째 방법보다는 효율성이 높고 빠르다.

DFS3
세번째 DFS는 배열 자체를 검사하는 로직을 추가한 방법이다. DFS(5)를 예시로 보면 DFS(5)는 DFS(3)+DFS(4)이고 DFS(4)은 DFS(2)+DFS(3)이다. 또한 DFS(3)은 DFS(1)+DFS(2)인데 이와 같이 DFS(5)를 구하기 위한 DFS(3)의 값을 구하고 DFS(4)의 값을 구하기 위해 DFS(3)의 값과 DFS(2)의 값을 또 구하게 된다. 그런데 여기서 배열에 검사하는 로직을 추가하여 배열에 DFS(3)와 DFS(2)의 값이 있기 때문에 DFS()를 실행하지 않고 바로 배열의 값으로 return하면 위 2개의 방법보다 훨씬 좋은 코드를 생산할 수 있다. 또한 이러한 방법을 메모이제이션을 사용했다고 한다.

fibonacci를 풀이하는 여러 방법.
코딩 인터뷰에서 많이 물어보는 방법이므로 알고 있으면 도움이 된다.

메모이제이션은 로직상 반복되어 계산되는 값을 저장해두어 프로그램 실행을 빠르게 하는 방법