Recursion, Memoization_피보나치

🔵 ThingsILearned

✔️ 메모이제이션

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때,
이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
동적 계획법의 핵심이 되는 기술

https://soheeparklee.github.io/posts/DS-memoization/

✅ Recursion, Memoization을 사용해서 피보나치 배열을 출력하세요

//⭐️input:
//7
//⭐️output:
//1 1 2 3 5 8 13

🟢 단순 재귀를 사용해서 풀기 1

class Main {
    public int DFS(int n){
        if(n<=1) return n;
        else{
           return DFS(n-2) + DFS(n-1);
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        for(int i=1; i<=n; i++){
            System.out.print(T.DFS(i) + " ");
        }
    }
}

🟢 단순 재귀를 사용해서 풀기 2

class Main {
    public int DFS(int n){
        if(n==1) return 1;
        else if(n==2) return 1;
        else{
           return DFS(n-2) + DFS(n-1);
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        for(int i=1; i<=n; i++){
            System.out.print(T.DFS(i) + " ");
        }
    }
}

//⭐️input:
//7
//⭐️output:
//1 1 2 3 5 8 13

👎🏻 재귀만을 사용했을 때 한계

하나하나씩 계산해서 출력하다보니
숫자 하나 나오고…기다렸다가 다음 숫자 나오고…또 기다리고…
끝까지 출력하는데 오래 걸림

🟢 재귀 사용하고, 배열에 값 저장해서 가져오기

👍🏻 배열에 값 저장하는 이유

배열에 값을 저장하지 않고 단순 재귀만을 사용해서 프린트하면
값 하나 나오고…계산해서 다음…또 계산해서 다음…하다보니
하나의 값을 얻고 그 다음 값을 얻기까지 시간이 오래 걸림.
배열에 모든 값을 저장하고 한번에 프린트하면,
처음에 모든 값을 계산하는 데 시간이 걸릴 수 있으나
한번에 모든 값을 출력할 수 있다는 장점이 있다.

💡 주의: 배열의 크기는 n+1

우리는 배열의 0번째 인덱스는 사용하지를 않는다. 따라서 배열의 0번째 인덱스는 버리고, 대신 n개 만큼의 자리가 필요하니 배열의 크기는 n+1

class Main {
    static int[] fibo; //배열 생성
    public int DFS(int n){
        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]= 1;
        else{
           return fibo[n]=  DFS(n-2) + DFS(n-1);
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        fibo= new int[n+1]; //배열의 크기는 n+1
        T.DFS(n);
        for(int i=1; i<=n; i++){
            System.out.print(fibo[i] + " ");
        }
    }
}

✅ 메모이제이션과 재귀함수를 사용해 빠르게 피보나치 구하기

class Main {
    static int[] fibo;
    public int DFS(int n){
        //memoization
        //배열에 이미 계산해 둔 값이 있는지 확인하고, 있으면 굳이 똑같은 계산을 두 번 하지는 않음
        if(fibo[n] != 0) return fibo[n];

        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]= 1;
        else{
           return fibo[n]=  DFS(n-2) + DFS(n-1);
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        fibo= new int[n+1]; //새로 배열을 만들면 처음에는 다 0으로 초기화 됨
        T.DFS(n);
        for(int i=1; i<=n; i++){
            System.out.print(fibo[i] + " ");
        }
    }
}


//⭐️input:
//7
//⭐️output:
//1 1 2 3 5 8 13

👍🏻 메모이제이션을 사용

n 숫자가 커질수록 시간이 엄청 오래 걸린다는 문제가 있다.
예를 들어 n 이 45라면, 가지쳐서 구하는 합이 엄청 많을 것이다.
이를 해결하기 위해 메모이제이션을 사용한다.
메모이제이션을 하면 이미 계산한 값을 배열에 저장하였으니,
값을 계산하기 전에 이미 배열에 계산해 둔 값이 있는지 확인한다.