4. 피보나치 재귀(메모이제이션)

1. 문제

피보나치 수열을 출력한다.

 

만약 7이 입력되면 1 1 2 3 5 8 13, 모든 항을 오름차순으로 출력한다.

 

 

2 . 나의 풀이

강의의 도움을 받으며 풀었다.

 

3 - 1. 강의 풀이

맨 마지막 항만 출력하는 건 쉽지만

모든 항을 오름차순으로 출력하는 건 재귀함수 내에서 출력만으로 풀 수 없다.

 

 

dfs(7)를 호출하면 위사진과 같이 17개의 재귀함수가 스택프레임 방식으로 호출되어 17개의 출력이 나오기 때문이다.

따라서 피보나치 배열을 별도로 만들어서 피보나치 항의 값을 배열에 저장한 다음

재귀함수가 종료되면 피보나치 배열을 출력하면된다.

하지만 결국 이 방식은 재귀함수를 호출 할 때 두 갈래로 계속 나뉘어 지면서 fb(2)와 fb(1)까지 내려가는 비효율점을 개선하지는 않는다.

 

이 방법을 개선하는 것이 메모이제이션이다.

즉, 이 전에 계산했던 값을 활용하는 것이다.

재귀함수 fb(n-1) + fb(n-2)를 호출하기 전에 피보나치 배열에 해당 값이 이미 계산되어있다면 그 배열의 값을 호출하면 된다.

 

코드에 if(fb[n] != 0) return fb[n]; 이 한줄만 추가하면 된다.

 

3 - 2. 강의 코드

1. 메모이제이션을 사용하기 전.

fb(45)를 호출하는데 약 4초의 시간이 걸렸다.

package BFS_DFS;
import java.util.*;


public class dfs04 {
    public static  int[] fbArr;
    public static int fb(int n) {
        if(n == 1) return fbArr[1] = 1;
        else if(n==2 )return fbArr[2] = 1;
        else return fbArr[n] = fb(n - 1) + fb(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //피보나치의 항과 배열의 항을 일치시키기 위해 0번째 인덱스는 사용하지 않음
        fbArr = new int[n + 1];
        fb(n);

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

 

2. 메모이제이션을 사용 후

fb(45) 호출 시 1초도 걸리지 않는다.

package BFS_DFS;
import java.util.*;


public class dfs04 {
    public static  int[] fbArr;
    public static int fb(int n) {
        //int 배열의 default 값은 0 이므로 0이 아니면 그 전에 값을 구해둔 것이다.
        if(fbArr[n] != 0) return fbArr[n];

        if(n == 1) return fbArr[1] = 1;
        else if(n == 2)return fbArr[2] = 1;
        else return fbArr[n] = fb(n - 1) + fb(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //피보나치의 항과 배열의 항을 일치시키기 위해 0번째 인덱스는 사용하지 않음
        fbArr = new int[n + 1];
        fb(n);

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

 

 

번외: for문을 활용한 피보나치 수열

package BFS_DFS;
import java.util.*;

public class dfs04 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] fv = new int[n + 1];
        fv[1] = 1;
        fv[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            fv[i] = fv[i - 1] + fv[i - 2];
        }

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

 

 

 

4. 얻어갈 점

피보나치 수열은 for문을 이용해 출력하는게 더 효율적이다.

재귀함수를 사용하면 스택 프레임이 계속 생겨나 비효율적인데 반해,

for문은 하나의 스택 프레임 안에서 반복문이 돌아가는 방식이기 때문이다.