[Ch.07 - Recursive] 04. 피보나치 수열 (+메모이제이션) #

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. 배열 이용
2. 재귀함수 이용
3. 메모이제이션 이용

1. 배열을 이용한 풀이

import java.util.Scanner;

public class Main {
	//피보나치 수열
	//앞의 2개의 수를 합해 다음 숫자가 되는 수열
	//항의 수: N 입력
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();


		for(int x : solution(n)) {
			System.out.print(x+" ");
		}
		kb.close();
		
	}
	static int[] solution(int n) {
		//1.ds
		int [] answer = new int[n];
		answer[0]=1;
		answer[1]=1;
		
		//2.for,while
		for(int i=2;i<n;i++) {
			answer[i]=answer[i-1]+answer[i-2];
		}
		
		return answer;
	}
	

}

2. 재귀함수만을 이용한 풀이

import java.util.Scanner;

class Main {

	// 피보나치 재귀
	// 앞에 두개 합쳐서 하나

	static 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) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		for (int i = 1; i <= n; i++) {
			System.out.print(DFS(i) + " ");
		}

		kb.close();
	}

}

3. Memoization을 이용한 풀이
메모이제이션
: 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법


+) 세련된 풀이
배열에 넣어서, 동일한 계산식은 배열에서 꺼내서 사용하는 방식

import java.util.Scanner;

public class Main {
	static int[] fibo;
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		fibo=new int[n+1];
		for(int i=1;i<=n;i++) {
			System.out.print(DFS(i)+" ");
			//배열의 첫 행부터 재귀함수 호출 -> 배열에 존재해야 가져오기 때문에 시간을 줄이기 위해
		}
	}
	static int DFS(int n) {
		if(fibo[n]>0)
			return fibo[n];
		//배열에 존재한다면, 배열에서 가져온다.
		
		//존재하지 않을 경우, 배열에 값을 넣는다.
		if(n==1 || n==2) {
			return fibo[n]=1;
		}
		else
			return fibo[n]= DFS(n-2)+DFS(n-1);
	}

}