[DFS,BFS 기초] 피보나치 재귀(메모이제이션)

문제

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

 

---

 

(아래 코드는 전체 정답 코드가 아닌 일부 코드이다)

 

여기서 DFS는 n번째 항을 구해주는 것이다

넘어온 n(항의 개수)이 1이면 1을 return 해준다

else if (n==2)일때도 1을 return 해준다

else return DFS(n-2)+DFS(n-1)은 n번째 항의 앞앞 값과 바로 앞의 값을 리턴해준다

 

 

설명하면, DFS(5)라는 값은 1 1 2 3 5 니까 5라는 값을 리턴받아야된다

5는 5의 앞앞 항과 5의 바로 앞 항을 더하는 것이다 그래서 D(3)과 D(4)를 더한 값을 리턴받는 것임 

그러면 D(3)은 D(1)과 D(2)를 더한 값을 리턴받아야 된다

D(4)는 D(2)와 D(3)을 더한 값을 리턴받아야 한다

 

여기서 문제처럼 계속 숫자를 출력하려면 for문이 돌아야 한다

 

 

그러려면 위처럼 수정해주면 된다.

 

그런데, 위처럼 코드를 짜면 n=45과 같은 값을 넣었을 때 성능이 너무 안 좋다. 개선하려면

static int[] fibo 배열을 추가한다.

 

fibo= new int[n+1]은 인덱스 번호를 넣어준다 0번 인덱스는 필요가 없다. n이 10이면 인덱스 10이 필요하기 때문에

그러면 T.DFS(n) 이렇게 한번만 호출해주면 된다 for문에서는 fibo[i] 이렇게 찍어준다

 

fibo[n]= DFS(n-2)+DFS(n-1);

여기서 n이 6이라고 치면 DFS(4)+DFS(5)를 두 값을 더해서 6번에다가 저장하고 return 하는 것

그니까 똑같이 리턴은 하는데 배열에다가 저장하고 나서 배열값을 리턴하는 것으로 바뀐 것

 

이렇게 코드 짜면 시간이 훨씬 단축되었다 그런데 

 

여기서 맨 아래 D(3)에서 D(1) D(2) 이렇게 또 뻗지말고, 왼쪽 위에서 이미 D(3)을 구한 값을 이용하는 것으로 바꾸면 좋다

그니까 또 똑같은거 구하지말고 미리 구해진 값을 리턴해주는 것으로 바꾸자

 

if (fibo[n]>0) return fibo[n]; 코드 추가해주면 이미 있는 값으로 리턴해줄 수 있다

 

그러면 최종 코드는 아래와 같다.

 

 

+ 사실 성능은 위처럼 재귀보다 for문으로 짜는게 성능이 더 좋다...