[백준] 10870. 피보나치수 5

 

https://www.acmicpc.net/problem/10870

 

 

풀이1

• 구조가 단순하지만 이미 계산한 fib(n-1)과 fib(n-2)를 다시 계산을 하여 중복 호출이 발생
• 시간 복잡도 : O(2ⁿ) (지수적 증가 → 비효율적)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fib(n));
    }
}

 

풀이2

• 이미 계산한 결과를 배열에 저장하여같은 값이 필요할 때는 다시 계산하지 않고 바로 반환 (메모이제이션 적용)
• 코드 복잡도는 조금 늘지만 속도가 압도적으로 빨라짐
• 시간 복잡도 : O(n) (한 번씩만 계산하므로 훨씬 효율적)

import java.io.*;
import java.util.*;

public class Main {
    static int[] memo = new int[21]; // n<=20
    static int fib(int n) {
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fib(n-1) + fib(n-2);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fib(n));
    }
}

 

메모이제이션(Memoization)

• 한 번 계산한 결과를 기억해두고 같은 입력이 들어올 때 저장된 값을 재사용하는 기법
• 재귀 함수에서 발생하는 중복 계산을 제거하기 때문에, 동적 프로그래밍(Dynamic Programming, DP)의 핵심 개념 중 하나