[Java] BOJ 2748 - 피보나치 수 2

Jae Chan·2023년 2월 3일

Coding-Test

목록 보기

7/10

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. >그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력 📨

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력 📩

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력

예제 출력

알고리즘 분류

수학
다이나믹 프로그래밍

문제 발생 ❗

예전에 피보나치 수열 관련 문제를 풀었었기에 재귀 함수를 이용해 풀어보려 했다.
근데 안 풀어질 거란 걸 알았다. 해당 문제는 90번째의 피보나치 수까지 구하라고 돼있는데 피보나치 수열은 30번째만 구해봐도 수가 832,040 이다.

재귀함수로 이를 구현하면 연산 속도가 매우 느려질거라 예상 됐지만 일단 재귀함수로 작성하고 제출을 해봤다.

public static long fibonacci(int A) {
       if(A == 0)
            return 0;
        else if(A <= 1)
            return 1;
         else
            return fibonacci(A - 2) + fibonacci(A - 1);
    }

이런 식으로 메소드를 만들고 제출해봤다.

아니나 다를까 시간초과가 났다. 그렇다면 어떻게 해결 해야할까? 🤔

우선 문제의 알고리즘 분류에 있던 다이나믹 프로그래밍(DP) 를 힌트로 삼아 정보를 찾아봤다.

다이나믹 프로그래밍(Dynamic Programming)

최적화 이론 의 한 기술이며 , 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적계획법 이라고도 부른다.

출처 : namu.wiki

즉, 하나의 큰 문제를 해결하기 위해 중복되는 하위 문제들의 값들을 기록 및 저장하여 문제를 해결하는 알고리즘이라고 한다. 피보나치 수열은 점화식f(n) = f(n - 1) + f(n + 2)이기 때문에 동적 계획법을 사용하기 원활하다고 볼 수 있다고 한다.

피보나치 수열 문제를 재귀함수를 해결한다고 하면

>>> 입력 값 5
fibonacci(1)
fibonacci(2)
fibonacci(1) + fibonacci(2)
fibonacci(2) + (fibonacci(1) + fibonacci(2))
fibonacci(1) + fibonacci(2) + (fibonacci(2) + (fibonacci(1) + fibonacci(2)))

이렇게 5의 값을 구한다 했을 때도 전에 연산했던 값이 계속 중복으로 들어간 것을 확인할 수 있다.

메모이제이션

메모이제이션(memoization) 은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. - 위키백과

이런 방법대로라면 재귀 함수처럼 중복 연산없이 저장된 값들을 즉시 꺼내서 사용할 수 있다는 것이다.

>>> 입력 값 5
DP[1] = fibonacci(1)
DP[2] = fibonacci(2)
DP[3] = DP[1] + DP[2] = fibonacci(3)
DP[4] = DP[2] + DP[3] = fibonacci(4)
DP[5] = DP[3] + DP[4] = fibonacci(5)

코드로 작성하면 다음과 같았다.

/* 문제에서 주어진 피보나치 수열 최대 값 : 90 */
public static long[] DP = new long[91];
    public static long fibonacci(int A) {
        if(A <= 2) {	//
            return 1;  //  여기 까진 기존 값과 같다.
            
        } if (DP[A] != 0) { // 
            return DP[A];   // 이미 계산한 값은 상위 값 계산할 때 바로 반환.
        }
        
        /* 계산하지 이외의 값(= 0) 들은 계산 후(재귀 호출)에 값을 배열에 저장.
        *  그리고 반환 해준다.
        */
        DP[A] = fibonacci(A - 1)  + fibonacci(A - 2);
        return DP[A];
    }

문제 해결 ✔️

package PythonSeries2;

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

public class Solution_2748 {
    public static long[] DP = new long[91];
    public static long fibonacci(int A) {
        if(A <= 2) {
            return 1;
        } if (DP[A] != 0) {
            return DP[A];
        }
        
        DP[A] = fibonacci(A - 1)  + fibonacci(A - 2);
        return DP[A];
    }

    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(String.valueOf(fibonacci(N)));
        br.close();
        bw.close();
    }
}