DFS 피보나치 수열 (메모제이션)

메모제이션이란?

메모이제이션는 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법이란 뜻이다.
(굉장히 static이랑 비슷한...)

메모제이션은 Top-down(하향식) 방식으로 n, n-1, n-2, ... 1까지 위에서부터 시작하는 방식이다. 동적 계획법(DP), DFS에서도 많이 사용된다.

즉, 메모제이션은 재귀호출 방식을 개선한 방법이다. 메모제이션을 하기에 앞서, 먼저 재귀호출을 이해해보자.

재귀호출이란?

자기가 자기를 호출하는 방식.
대표적으로 stack이 이 구조로 되어있다.

재귀호출의 가장 좋은 예시가 피보나치 수열 or 팩토리얼 수열이다. 나는 가장 간단한 피보나치 수열로 정리해 보았다.

재귀함수로 푼 피보나치수열

public class FibonacciDFS {
    public int DFS(int n) {
        // 종료 조건
        if (n==1 || n==2) return 1;
        else {
            return DFS(n-1)+DFS(n-2);
        }
    }

    public static void main(String[] args) {
        FibonacciDFS T = new FibonacciDFS();

        for(int i=1; i<=n; i++){    // 1부터 시작
            System.out.print(T.DFS(i)+" ");
        }
    }
}

아래 사진은 함수를 `스택` 자료구조에서 함수를 호출하는 형태로 쌓이고(push) 나가는(pop) 모습을 보여준다.

개선된 피보나치 수열(by 메모제이션)

: 메모제이션을 사용, Array에 저장하고 이미 계산된 것은 재사용해서 처리속도가 높아진다!

// 4. 피보나치(DFS) -> 배열보다 성능이 안좋아 재귀호출은 상당한 메모리 잡아먹어
public class FibonacciDFS {
    static int[] fibo;		// class 밑에 전역변수로 배열 생성
    
    public int DFS(int n) {
        if(fibo[n] > 0) return fibo[n];     // 메모제이션 key : 이코드 없고 있고의 성능차이가 확실함! 왼쪽 트리 값을 미리 기록해서 return
        if(n == 1) return fibo[n]=1;
        else if(n == 2) return fibo[n]=2;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        FibonacciDFS T = new FibonacciDFS();
        int n = 45;     // 45면 엄청 버퍼링 -> 메모제이션 필요! static int[] fibo;
        fibo = new int[n + 1];   // 1부터 시작
        T.DFS(n);
        for(int i=1; i<=n; i++){    // 1부터 시작
//            System.out.print(T.DFS(i) + " ");
            System.out.print(fibo[i] + " ");
        }

    }

}

Bottom-up & Array로 푼 피보나치수열

• Bottom-up방식으로 0,1,2,... 부터 시작해서 해결한다.
• 메모제이션은 Array에 담아서 재사용하여 메모리 낭비를 줄이는 방식이다.
• Array(메모제이션)로 푼것이 재귀함수보다 더 성능이 좋다.
  아래 예시를 보자.

public class Fibonacci {

    private int[] solution(int n) {

        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i < n; i++) { //10 -> 2~9
            arr[i] = arr[i-2] + arr[i-1];		// 메모제이션 담아둬서 다음 호출할 때 재사용한다.
        }
        return arr;
    }

    public static void main(String[] args) {

        Fibonacci main = new Fibonacci();

        Scanner si = new Scanner(System.in);
        int N = si.nextInt();

        for(int x : main.solution(N))
            System.out.print(x+" ");
    }
}