자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 피보나치 재귀 (메모이제이션)

 

 

https://hyejin.tistory.com/1255

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 팩토리얼

-> 이전 문제 풀이 

 

 

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

설명

1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.

2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

 

입력

첫 줄에 총 항수 N(3<=N<=45)이 입력된다.

 

출력

첫 줄에 피보나치 수열을 출력합니다.

 

예시 입력 1 

10

 

예시 출력 1

1 1 2 3 5 8 13 21 34 55

 

 

문제 풀이  1

public int DFS(int n)
{
   if (n >= 3)
   {
      return DFS(n - 2) + DFS(n - 1);
   }else {
      return 1;
   }
}

👩‍💻 : 나는 우선 DFS(10) 의 값이 55라는 것까지는 구했는데 이걸 어떻게 출력해야할지 모르겠어서.. 여기까지만 해결하고 강의를 틀었다.. ㅎㅎ 

함수 사이에 출력을 두면 각각 함수 출력할때마다 처음부터 끝까지 출력하기 때문에 원하는 결과를 얻을 수 없었다. 

 

 

문제 풀이  2

// 강사님 풀이 1 : for 문을 활용한 풀이
public int DFS2(int n)
{
   if (n == 1)
      return 1;
   else if (n == 2)
      return 1;
   else
      return DFS2(n - 2) + DFS2(n - 1);
}

👾 : 강의를 듣는데 첫번째 풀이는 나와 동일하게 이렇게 진행하고는... 

 

long start = System.currentTimeMillis();
System.out.println("== for문 활용 =="); // ex) n = 45 이다? 그럼 엄청 시간이 걸릴 것이다..;; 점점 느려짐 (n의 값이 커질수록 오래 걸림)
for (int i = 1; i <= n; i++)
{
   System.out.print(fibonacciSequence.DFS2(i) + " " );
}
long end = System.currentTimeMillis();
System.out.println();
System.out.println("걸린 시간 : "  + (end - start) + "(ms)");

메인에서 이렇게 for문을 돌려서 결과를 출력했다..! 

아니 for문을 통해서 해도 되는지 몰랐네.. ㅋ 무조건 재귀 함수 내에서 해결해야 하는 줄... 

 

근데 물론 이렇게 풀면 n의 값이 적을 때는 금방 끝나지만 n의 값이 점점 커질 경우에는 시간이 점점 오래 걸린다. 

예시로 n = 45 로 돌려보는데 생각보다 시간이 꽤 걸리길래 시간 측정을 해봤는데 5초가 넘는 시간이 걸렸었다. 

걸린 시간 : 5489 ms 

 

 

문제 풀이  3

static int[] fibo;

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

 

👾 : 강사님이 푼 두번째 방식은 staic 배열을 활용해서 문제를 푸는 것이었다. 

먼저 static fibo 배열을 선언하고, n 값을 입력받을 때 해당 배열을 초기화해준 다음, 

 

배열에 DFS(1) = 1 이면 fibo[1]에 1 값을 저장하고,... DFS(3) 이면 DFS(1) + DFS(2) 한 값 2를 fibo[2]에 2를 저장한다. 

 

start = System.currentTimeMillis();
fibonacciSequence.DFS3(n);
System.out.println("== static 배열 활용 (1) ==");
for (int i= 1; i<= n; i++)
{
   System.out.print(fibo[i] + " ");
}
end = System.currentTimeMillis();
System.out.println();
System.out.println("걸린 시간 : " + (end - start) + "(ms)");

이렇게 배열에 값을 저장해준 다음, for문을 활용해서 해당 결과값을 출력해주면 된다. 

그러면 첫번째 풀이보다는 그나마 걸리는 시간이 조금 걸린다 ! 

걸린 시간 : 2443 ms 

 

 

문제 풀이  4

// 강사님 풀이 3 : 메모이제이션을 활용한 풀이 (시간복잡도를 확 줄여봄)
public int DFS4(int n)
{
   if (fibo2[n] > 0) {
      return fibo2[n];
   }
   else if (n == 1) {
      return fibo2[n] = 1;
   }
   else if (n == 2) {
      return fibo2[n] = 1;
   }else {
      return fibo2[n] = DFS4(n-2) + DFS4(n-1);
   }
}

👾 : 사실 두번째 풀이도 시간을 많이 줄이긴 했지만 걸리는 시간을 훨씬 줄이는 방법이 있다..! 

그 방법은 두번째 풀이처럼 먼저 static 배열을 사용하는데 이때, 배열에 이미 값이 저장되어 있다면 해당 값을 그냥 return 하는 것이다. 이렇게 되면 계속 값을 구하고, 하지 않아도 되기 때문에 걸리는 시간이 훅 줄어든다. 

걸린시간 : 1 ms 

 

-> 이렇게 무한 반복해서 구해야하는 값들이 많기 때문에 배열에서 이미 해당 값이 있다 하면 그 값을 return 해주면 시간이 많이 줄어든다 !