[Java] 2단계. 피보나치 수 5 [10870번]

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

• 예제 입력1

10

• 예제 출력1

55

---

• 문제 접근
  • 0과 1부터 시작하고 2번째 수부터는 앞의 두 수를 더한 값 
  • 입력
    • 자연수 n ( 0 <= n <= 20)
  • 출력
    • n번째 피보나치 수
• 문제 해결
  
  • 아래의 표를 보면 n = (n - 1) + (n - 2)의 공식이 생김
  • 종료 조건
    • n = 1이면 return 1
    • n = 0이면 return 0

피보나치 수 0 ~ 10 = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
2번째 피보나치 수	0(0번째) + 1(1번째) = 1 (2번째)
3번째 피보나치 수	1(1번째) + 1(2번째) = 2 (3번째)
4번째 피보나치 수	1(2번째) + 2(3번째) = 3 (4번째)
5번째 피보나치 수	2(3번째) + 3(4번째) = 5 (5번째)
6번째 피보나치 수	3(4번째) + 5(5번째) = 8 (6번째)
7번째 피보나치 수	5(5번째) + 8(6번째) = 13 (7번째)
8번째 피보나치 수	8(6번째) + 13(7번째) = 21 (8번째)
9번째 피보나치 수	13(7번째) + 21(8번째) = 34 (9번째)
10번째 피보나치 수	21(8번째) + 34(9번째) = 55 (10번째)

• 기존 풀이 [메모리 : 14,132 KB / 시간 : 104 ms]

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

    System.out.println(result);
}

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

 

• 문제점
  • 위의 코드가 백준 알고리즘에서 정답으로 나오기는 하지만, 이는 매우 비효율적인 코드임
    • n = 10일 때, fibonacci(9) + fibnonacci(8)
    • n = 9일 때, fibonacci(8) + fibnonacci(7)
    • n = 8일 때, fibonacci(7) + fibnonacci(6)
    • ...
  • 위처럼 이미 한 번 호출했던 함수를 계속해서 부르기 때문에 n이 최대 20이 아니라 훨씬 큰 수라면 StackOverFlow가 발생할 수 있을거라 생각 됨
  • n = 50일 때만해도 거의 75초나 소요되었음 
  • 이를 해결하기 위해서 메모리제이션(Memoization) 또는 동적계획법(DP)이 필요함

• DP 풀이 [메모리 : 14156 KB / 시간 : 100 ms] → Bottom-Up 방식

static int[] fiboArr;
public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    fiboArr = new int[n+1];
    if(n >= 1) {
        fiboArr[1] = 1; // 만약 n = 0이면 에러가 발생하여 조건문 추가
    }
    fibonacci(n);
    System.out.println(fiboArr[n]);
}

private static void fibonacci(int n) {
    for(int i = 2; i <= n; i++) {
        fiboArr[i] = fiboArr[i - 1] + fiboArr[i - 2];
    }
}

• 메모이제이션 풀이 [메모리 : 14,164 KB / 시간 : 104 ms] → Top-Down 방식

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

private static int fibonacci(int n) {
    if(n <= 1) return n; // 1이하라면 그대로 n 그대로 반환
    if(fiboArr[n] != 0) return fiboArr[n]; // 이미 계산된 값이면 그대로 반환
    return fiboArr[n] = fibonacci(n - 1) + fibonacci(n - 2);
}