피보나치 수열

일반적인 재귀함수로 푸는 경우

import java.util.*;
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();
        Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=1; i<=n; i++) System.out.print(T.DFS(i)+" ");
	}	
}

구했던 피보나치수열을 구하고 구하고 계속 반복해서 구하기 때문에 실행시간이 n이 커질수록 기하급수적으로 는다.

메모라이제이션으로 푸는경우

import java.util.Scanner;

public class Quiz4 {
    static int[] fibo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        fibo=new int[n+1];
        DFS(n);
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" ");
    }

    private static 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);
    }
}

fibo 라는 배열에 이미 구한수를 다시 구하지 않고 저장되있던 수를 다시 활용하여 쓰기 때문에 숫자가 늘어나도 실행시간이 기하급수적으로 늘지 않고 최적화된 모습을 보여준다.