자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Recursive_피보나치 재귀(메모이제이션))

 

 

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

 

예시 입력 1 

10

예시 출력 1

1 1 2 3 5 8 13 21 34 55

 

피보나치 수열은 2가지 방법으로 풀 수 있습니다.

 

1. 배열로 for문 사용

2. 재귀로 풀기

 

둘중에 어떤게 성능이 더 좋은가? 당연히 1번이다.

재귀는 함수가 하나 호출될때마다 스택 프레임이 생겨서 메모리 낭비도 많이 되고 무거워서 성능이 더 안좋다.

for문은 함수 하나를 만들었을 경우 스텍 프레임 하나만 가지고 돌기 때문에 그 안에서 지역변수, 배열만들어서 도는 것이다.

 

특정 항의 값을 리턴해주는 방법(피보나치 수열의 n번째 항만 리턴)

1. n은 몇번째 항인지를 의미한다.

2. 첫번째항과 두번째 항은 1을 리턴한다

3. 3번째 항부터 앞에 있는 2개 항을 더해준다.

public class Test {

    public int DFS(int n){
        if(n == 1) return 1; // 첫번째 항일 경우
        else if (n == 2) return  1; // 두번째 항일 경우
        else return DFS(n-2) + DFS(n-1); // 앞에 2개 항을 더해줌
    }
    public static void main(String[] args) {
        Test T = new Test();
        int n = 5;
        System.out.println(T.DFS(n));
    }
}

// 출력
5
// n이 6일 경우
8
// n이 7일 경우
13

 

 

피보나치 수열로 반환 

하지만 n이 커질 수록 재귀가 엄청 뻗어나가므로 성능이 좋지 않다.

어느 순간부터 점점 느려지더니, 마지막 45번째에는 리턴값 나올때 까지 5초정도 걸린다.

for문 순회하면서 매번 DFS를 호출하기 보다 원하는 값 한번만 호출하면 다 알 수 있다.

하지만 중간중간 값들을 저장해놔야 합니다.

public class Test2 {
    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) {
        Test2 T = new Test2();
        int n = 5;
        // 첫번째 항부터라서 1부터 시작.
        for (int i = 1; i <= n ; i++) System.out.print(T.DFS(i)+ " "); // DFS호출 5번 발생
    }
}

// 출력
1 1 2 3 5

 

피보나치 수열로 반환 - 성능개선 1

1. DFS호출을 한번 하는데, 기능 수행하면서 fibo배열에 전부 값을 저장해두고 출력할때 하나씩 꺼낸다

2. 한번에 모든 수열을 출력하는데 8초정도 걸리긴 하지만, 이전 코드처럼 하나 출력하는데 3~5초 정도 걸리지 않는다.

public class Test3 {
    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) {
        Test3 T = new Test3();
        int n = 10;
        // 첫번째 항이 1이니까 fibo 1번 인덱스에 해당 값을 넣어주기 위해 n+1
        // 0번 인덱스는 사용 안함
        fibo = new int[n+1];
        T.DFS(n);
        for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
    }
}

// 출력
1 1 2 3 5 8 13 21 34 55

 

 

피보나치 수열로 반환 - 성능개선 2 (메모이제이션)

1초도 안걸리게 출력한다.

기능이 수행되면서 return받을때 fibo배열 안에 기록을 하고 있기 때문에,

다시 똑같은 재귀를 호출하는게 아니라 fibo에 값이 들어있는 것을 활용해서 시간복잡도를 확 줄인다.

public class Main {
    static int[] fibo;
    public int DFS(int n){
        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();
        int n = 10;
        fibo = new int[n+1];
        T.DFS(n);
        for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
    }
}