[백준_DP]2747_피보나치 수

오늘부터 다시 알고리즘을 조금씩 풀어야겠다는 생각이 들었다.

그래서 초심자의 마음으로 시작한 문제 '피보나치 수...!!'

자료구조나 알고리즘 수업을 들으면, 가장 먼저 배우는 내용이 아닐까 생각한다.

위에 설명된것 처럼

F(N) = F(N-1) + F(N-2) 가 된다.

즉 과거에 만들어진 값을 다시 재활용하여 사용하는 효율적인 방법으로 풀 수 있다랄까...?

무튼, 그러한 방법론이 '동적 계획법'

즉, Dynamic Programming 이라고 한다.

DP를 구현하기 위한 방법으로는 Top-Down 방식과 Bottom-Up 방식이 존재한다.

나 같은 경우는 DP에 약하기 때문에 보통 for문을 돌려 푸는 Bottom-Up 방식을 선호한다....

쉽게 말하면, for문을 돌려 필요한 값들을 먼저 구하는 방식이다.

위 문제를 예로 들어보자

F[0] = 0, F[1] = 1 이라고 초기 값이 주어진다.

그럼 우리는 F[2]를 구하기 위해서 F[0]과 F[1]을 더해야만 한다.

그럼 이렇게 생각 할 수 있다.

"다음 수를 구하기 위해서는 이전에 구했던 수가 필요하구나? 그럼 이전에 구했던 수를 저장해놔야겠다."

그렇게 되면 우리는 F[100]을 구하기 위해서 이전에 미리 구해놓은 F[99] + F[98] 만 더해주면 된다.

왜냐하면 값을 저장해놨으니까!

그래서 DP문제는 주로 배열을 사용하여, 미리 구한 값들을 저장한다.

그림으로 보도록 하자.

이 방법을 코드로 표현하면 이렇게 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Al2747 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[] fibonacci = new int[46];
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        
        for (int i = 2; i < fibonacci.length; i++) {
            fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
        }
        
        System.out.println(fibonacci[N]);
    }
}
 

이 문제를 시작으로 다시 알고리즘 빡공 고고~~