피보나치 수열(재귀함수 이용)

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

 

 

---

 

💡 코딩 인터뷰에서 피보나치수열을 배열, 재귀 함수로 구현 후 성능 비교하라는 문제를 자주 출제합니다.
   + 성능은 배열(for문 이용)이 더 좋습니다. - 스택 프레임에 하나 생겨서 거기서만 돌고 끝남
      재귀의 경우 함수 호출될 때마다 스택 프레임에 (메모리에) 쌓여서 성능이 안 좋습니다. 

이전 백준 문제를 풀 때는 배열을 이용해서 풀었었는데요, 비교해서 보시는 것을 추천합니다.

[백준 10870번] 피보나치 수 5

[백준 10870번] 피보나치 수 5

 

 

코드 구현 1 : 출력 시 중간중간 멈춤, 8초

public 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();
		// n : 항의 번호
		int n=10;
		for(int i=1; i<=n; i++) {
			System.out.print(T.DFS(i) + " ");  
		}
	}
}

이 코드의 문제점은 시간이 너무 많이 걸린다는 것입니다. 

지금은 n=10이기에 빠른 시간 내에 출력이 되는 것처럼 보이지만 만약 n=45라면 훨씬 오래 걸립니다.(총 8초 정도)

 

이를 조금 더 빨리 하기 위해서는 n만 호출하는 방법이 있습니다. 

대신 그 전의 값들을 배열을 만들어 기록해두어야 합니다. fibo[ ]

 

 

코드 구현 2 : 5초

public 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;
		// 0번 인덱스 필요없음, 10번 인덱스 필요함
		fibo = new int[n+1];
		// n만 호출
		T.DFS(n);
		for(int i=1; i<=n; i++) {
			System.out.print(fibo[i] + " ");  
		}
	}
}

한 번 호출로 변경했지만 이 또한 시간이 너무 많이 걸리는 것을 알 수 있습니다.(총 5초)

 

메모이제이션을 활용해서 1초 만에 나오도록 수정해보도록 하겠습니다!

 

 

코드 구현 3 : 메모이제이션 활용

public class Main {
	static int[] fibo;
	public int DFS(int n) {
		// 메모이제이션 활용,  fibo[n]>0 것은 이전에 값을 구해뒀다는 의미 
		if(fibo[n]>0) return fibo[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] + " ");  
		}

	}

}

 

 

구현 코드 1 → 구현 코드 2 → 구현 코드 3으로 갈수록 시간 복잡도가 줄어듭니다.