[문제풀이] 07-04. 피보나치 수열(재귀)

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0704. 피보나치 수열(재귀)

🗒️ 문제

🎈 나의 풀이

	 private static int DFS(int n) {
        if(n <= 2) return 1;
        else return DFS(n - 1) + DFS(n - 2);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1; i<n; i++) System.out.print(DFS(i) + " ");
    }

🖍️ 강의 풀이

  static int[] fibo;
	public int DFS(int n){
		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.print(fibo[i]+" ");
	}

💬 짚어가기

피보나치 수열의 n번째 수는 n-1와 n-2번째 수를 합한 값이다. 따라서 n번째 수를 구하기
위해선, 이전의 n-1까지의 수열을 구해야한다.

나의 풀이에서는 반복문을 통해 1부터 n까지의 피보나치 수열을 구한다. 이 방식의 경우 n이
커짐에 따라 필요한 재귀 연산의 수가 기하급수적으로 늘어난다.

메모이제이션 (Memoization)
강의에서의 이전 연산의 결과를 보관할 수 있는 배열을 두고 확인하는 방식으로 중복된 연산 과정을
생략한다. 이 같이 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에
저장하고 중복 계산을 제거하여 전체 실행속도를 빠르게 해주는 기법을 메모이제이션이라 한다.