섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 4. 피보나치 재귀(메모이제이션)

문제

• 피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
• 입력은 피보나치 수열의 총 항의 수이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

입력

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

출력

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

입출력 예제

---

풀이방식

이번 문제는 재귀함수를(을) 사용하여 푸는 문제이다.

재귀함수란 자기가 자기 자신을 호출하는 함수이며, 스택 프레임을 사용한다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

피보나치 수열은 for문과 재귀중에 for 문으로 푸는게 효율이 훨씬 좋다.

재귀는 스택 프레임이 매번 생성되기 때문이다.

하지만 지금은 재귀함수를 배우는 과정이므로 재귀를 통해 풀어보자.

---

설계과정

1. N이 1이거나 2이면 1을 리턴한다.

2. 그게 아니라면 앞의 두 수를 더하여 N번째의 수를 구한다.

3. 단, N번째의 값이 0보다 크다면 그 값을 그대로 출력한다.

---

 

풀이과정

1. int 형의 배열 fibo[ ] 를 전역변수로 선언한다.

• 메소드 구현과 출력, 모든 부분에서 사용해야 하므로 전역으로 선언한다.

2.  fibo[ ] 배열은 N+1 크기로 선언한다.

• 1번부터 N번까지의 인덱스 번호가 필요하기 때문이다.

3. 메소드 구현으로 넘어가보자.

 

4. fibo[N] 의 값이 0보다 크다면 그 값을 그대로 리턴한다.

• 이미 구해진 값이 있다면 그 값을 바로 리턴하여 시간복잡도를 줄이기 위함이다.
• 이와 같은 방식은 메모리제이션이라고 부른다.
• 아래 이미지를 통해 자세히 이해해보자.

---

먼저 트리를 통해 어떤 값들이 더해져서 다음 값이 만들어지는지 확인해보자.

여기서 DFS(5)를 확인해보자.

DFS(5) 값을 구하기 위해서는 DFS(3)와 DFS(4) 값을 더해야 한다.

그런데 DFS(3)은 DFS(4)를 구할 때에 이미 값이 한번 나왔다.

이 때 구해진 DFS(3)의 값을 DFS(5)를 구할 때에 다시 사용하면, 반복계산하는 과정이 사라지게 된다.

이러한 과정을 메모리제이션이라고 한다.

---

5. N이 1이거나 2이면 1을 리턴한다.

• 피보나치 수열에서 1번째와 2번째 값은 무조건 1이기 때문이다.

6. 그 외에는 fibo[N]에 앞의 두 수를 더한 값을 저장한다.

 

7. 결과를 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.