피보나치 수열

첫번째와 두번째는 1 세번째부턴 fib(n-1) + fib(n-2) 형태

그냥 재귀로 구현하면 효율이 많이 떨어진다

 

public int dfs(int n){
	if(n == 1) return 1;
	else if(n == 2) return 1;
	else return dfs(n-1) + dfs(n-2);
}

 

개선을 위해 메모리제이션(한번 사용한 값을 기억) 해두기

 

배열을 선언하고 dfs 함수를 사용하면 배열 해당 인덱스에 피보나치의 값이 들어가게 한다, 이미 그 값이 있으면 재귀를 하지 않고 배열 값을 리턴한다

 

        if(fib[n] > 0 ) return fib[n];
        if(n == 1) return fib[n] = 1;
        else if(n == 2) return fib[n] = 1;
        else{
            return fib[n] = dfs(n-1) + dfs(n-2);
        }

위 형태로 배열에 값을 넣어서 리턴하는 게 가능하다!

import java.util.*;

class Main {
    //피보나치 수열의 값을 저장해둘 배열 fib
    static int[] fib;
    public int dfs(int n){
        //메모리제이션, 이미 fib 배열에 값이 들어 있으면 밑에 dfs로 재귀를 하지 않고 바로 그 값을 리턴
        if(fib[n] > 0 ) return fib[n];
        if(n == 1) return fib[n] = 1;
        else if(n == 2) return fib[n] = 1;
        else{
            return fib[n] = dfs(n-1) + dfs(n-2);
        }
    }

    public static void main(String[] args) {
            Main T = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            //fib 배열엔 1~n번 들어감
            fib = new int[n+1];
            T.dfs(n);
            for (int i = 1; i<= n; i++) System.out.print(fib[i] + " ");
    }
}