[재귀, 메모리제이션] 4. 피보나치수열

<<풀이>>

 

풀이 1

: 이 풀이는 i 값이 변할때 마다 DFS가 돌면서 피보나치수열을 수행한다. 그렇기 때문에 n의 숫자가 작을때는 체감을 못하지만, n 값이 예를들어 45이면 결과값이 나오기 까지 시간이 많이 걸린다.

import java.util.*;

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();
        int n = 7;
        for(int i = 1; i <= n; i++) System.out.println(T.DFS(i) + " ");
    }
}

 

 

 

풀이2

: 위의 풀이 1 방식을 개선해서 시간 복잡도를 줄인 풀이이다. 우리가 구하고자 하는 값이 n 이 10인 피보나치 수열을 만들고자 할 때, 알고리즘 형태상 n = 10을 넣어주면 이미 피보나치 수열이 한 번 완성이 된다. 그러면 그 값을 미리 배열에 넣어두고 출력하는 방식이다. 즉, 풀이 1처럼 했던 과정을 n = 10을 넣어줌으로써 i 값에 따른 계산을 반복할 필요가 없어진다. 

import java.util.*;

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();
        int n = 45;
        fibo = new int[n + 1];
        T.DFS(n);
        for(int i = 1; i <= n; i++) System.out.println(fibo[i] + " ");
    }
}

*같은 클래스의 static은 메서드 또는 필드 그 자체로 이용이 가능하다. (일반적으로는 static이 아니면 static내부에서 사용하기 위해서는 객체 생성이 필요하다.)

 

 

풀이3(*메모리제이션)

: 우선 이 방식을 이용하면 풀이 2 보다 월등히 빠르다. 이는 값을 구하면 그 값을 저장해두다가, 그 값을  한 번 더 구해야 하는 상황이 나오게 되면 계산하지 않고 바로 저장되어 있는 값을 다시 가져와서 사용하는 것이다. 

이를 풀이 2에서  if(fibo[n] > 0) return fibo[n];을 추가하여 구현했다.  이를 우리는 "메모리제이션" 이라고 한다.

import java.util.*;

class Main {
    static int[] fibo;
    public int DFS(int n) {
        if(fibo[n] > 0) return fibo[n]; //fibo 배열의 기본 디폴트 값은 0이기 때문에 '> 0'으로 비교하여 구할 수 있다.
        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 = 45;
        fibo = new int[n + 1];
        T.DFS(n);
        for(int i = 1; i <= n; i++) System.out.println(fibo[i] + " ");
    }
}

 

 

 

<<추가 공부>>

 

for문 vs 재귀함수(Stack 프래임)

 

=> for문이 훨씬 좋다. 우선 for문 같은 경우는 Stack이 한 번 생성되어 작동하지만, 재귀함수는 Stack 이 여러개 쌓이고 하나씩 처리하면 날리는 형식이다. 그렇기 때문에 시간 복잡도 부분에서 for문이 훨씬 좋다.