[Java알고리즘] 7-4. 피보나치 재귀(메모이제이션)

🌼 Problem

🍪 강사 Solution - for문 사용할줄이야...

import java.util.Scanner;

public class _74_피보나치수열 {

    public static int Solution(int n){

        if(n==1) return 1;
        else if(n==2) return 1;
        else{
            Solution(n-1);
            return Solution(n-2)+Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        for(int i = 1; i <= input; i++){
            System.out.print(Solution(i)+ " ");
        }
    }
}

[결과]

🍪 강사 Solution2 - 리팩토링(배열 사용)

import java.util.Scanner;

public class _74_피보나치수열 {

    static int[] fibo;

    public static int Solution(int n){

        if(n==1) return  fibo[1] = 1;
        else if(n==2) return fibo[2] = 1;
        else{
            Solution(n-1);
            return fibo[n] = Solution(n-2) + Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        fibo = new int[input+1];
        Solution(input);
        for(int i = 1; i <= input; i++){
            System.out.print(fibo[i]+ " ");
        }
    }
}

매번 Solution()을 호출할 필요 없이, 한 번만 호출하고 fibo[]에 저장한다.
결과값은 fibo[] 배열에 저장된 값을 for문으로 출력하므로, 실행 속도가 빨라진다.

🍪 강사 Solution3 - 리팩토링(메모이제이션 사용)

import java.util.Scanner;

public class _74_피보나치수열 {

    static int[] fibo;

    public static int Solution(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{
            Solution(n-1);
            return fibo[n] = Solution(n-2) + Solution(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();

        fibo = new int[input+1];
        Solution(input);
        for(int i = 1; i <= input; i++){
            System.out.print(fibo[i]+ " ");
        }

    }
}

[결과]

if(fibo[n]>0) = fibo[n] 값이 이미 존재한다면,
다시 연산할 필요없이 return fibo[n]을 해주기 때문에 속도 효율이 굉장히 증가한다.