[알고리즘_Java] 백준 10870번 피보나치 수 5 (재귀, 메모이제이션)

---

 

 

<재귀>

-> 함수 여러번 호출 방식

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       bw.write(pibo(n)+"");
       bw.flush();
    }

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

 

<메모이제이션>

-> 배열에 값을 저장해서 호출 방식

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int f = Integer.parseInt(br.readLine());
        fibonacci(f);
        bw.write(fibonacci(f)+"");
        bw.flush();
    
    }

    public static int fibonacci(int f){
        if(f==0){
            return 0;
        }else if(f==1){
            return 1;
        }else {
            int[] arr = new int[f+1];
            arr[0] = 0;
            arr[1] = 1;

            for (int i = 2; i <= f; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            }

            return arr[f];
        }
    }
}

---

두 방법 다 괜찮아 보이는데 메모이제이션(배열) 방식이 값이 배열에 저장되니까 함수를 여러번 반복하지 않아도 되고 효율적인 듯하다.