피보나치 수열 - 메모제이션

• 메모제이션을 활용한 피보나치 수열
• 이미 계산한 내용들을 저장해 두고, 연산할 필요없이 저장된 데이터를 불러오는 것이다.
• 메모제이셔늘 쓰게 되면 기존 O(2^N)에서 O(N)으로 급격하게 줄어든다.

data[1] = fibo(1)

data[2] = fibo(2)

data[3] = data[1] + data[2] = fibo(3)

data[4] = data[2] + data[3] = fibo(4)

data[5] = data[3] + data[4] = fibo(5)

 

• 소스 

package org.kyh.codeup;

import java.util.Scanner;

public class p1905 {

    static int[] data;
    //static int sum = 2;

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int target = scan.nextInt();

        data = new int[target+1];

        int result = fibo(target);

        System.out.println( result );

    }

    // 1 1 2 3 5 8 13 21 34 ...
    public static int fibo(int x){

        if(x <=2){
            return 1;
        }

        if(data[x] != 0){
            return data[x];
        }else{
            data[x] = fibo(x-1) + fibo(x-2);
            //sum += data[x];

            return data[x];
        }


    }
}