메모이제이션

재귀함수 구현을 통해 메모이제이션을 이해해보기

 

 

피보나치 수열의 각 항을 출력하는 프로그램을 만들어보자

 

✅ 1단계: 재귀함수로 피보나치 수열 구현해보기

package 섹션7;

import java.util.Scanner;

public class Q1_재귀함수 {

    static int fibbo(int n){
        if(n==1) return 1;
        else if (n==2) return 1;
        else return fibbo(n - 2) + fibbo(n - 1);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();

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

 

일반적인 재귀함수 형태로, for문을 이용하여 계산 결과값을 하나하나 출력할 수 있다. 

하지만 이 방식을 사용하게 된다면 항의 개수(n)의 값이 커지게 되면서 계산 속도가 매우 느려지게 된다. 

 

왜냐하면 위의 코드를 이용해서 5개의 피보나치 수열의 값을 출력하기 위해서는 아래의 그림처럼 모든 값들을 누적해서 다시 계산해야한다. 

fib(3)을 구하기 위해 아래에 있는 값들을 계산하고, fib(2)를 구하기 위해 아래에 있는 값들을 계산한다.

그리고 다시 fib(4)를 구하기 위해 fib(3)을 누적해서 계산하고 fib(2)를 누적해서 계산한다. 

 

그렇기 때문에 for문을 이용하여 각 항의 값을 하나하나 구하는 방식으로 구현한다면, 시간 복잡도가 매우 커지게 된다. 

따라서 각각의 항의 값을 계산하고 "배열"에 따로 저장해둬서 배열의 값만 마지막에 for문으로 출력되도록 바꿔보자. 

 

 

 

 

✅ 2단계: 배열을 이용하여 항의 값을 저장해두기

import java.util.Scanner;

public class Q1_재귀함수 {

    static int[] arr; // 피보나치 수열의 각 항의 값을 저장하는 배열
    
    static int fibbo(int n){
        if(n==1) {
            return arr[n]=1;
        }
        else if (n==2) {
            return arr[n]=2;
        }
        else {
            return arr[n]=fibbo(n - 1) + fibbo(n - 2);
        }
    }

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

        int n = sc.nextInt(); // 항의 수
        fibbo(n);
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

 

배열에 항의 값을 저장해두고, 마지막에 배열의 값만 출력함으로써 시간 복잡도가 줄어들었다. 

여기서 더 나아가면, 이미 재귀함수를 반복할때 배열의 값을 확인하여 이미 값이 들어있다면 재귀함수를 호출하지 말고, 배열의 값을 리턴하도록 코드를 수정해준다면 중복적으로 계산해야하는 것들이 매우 줄어들게 된다. 

 

 

✅ 3단계: 메모이제이션 

 

 

 

package 섹션7;

import java.util.Scanner;

public class Q1_재귀함수 {
    static int[] arr;
    static int fibbo(int n){

        // 메모이제이션: 이미 문제를 풀어봤는지 확인하기
        if(arr[n]>0) return arr[n];

        if(n==1 || n==2) return arr[n]=1;
        else return arr[n]= fibbo(n - 2) + fibbo(n - 1);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        arr=new int[n+1];

        fibbo(n);
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

 

 

피보나치 수열을 계산하기 전에, 배열에 값이 있는지 확인해봄으로써 중복적인 연산을 피할 수 있다. 

if(arr[n]>0) return arr[n];

 

 

 

 

 

 

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션