백준 24416 알고리즘 수업 - 피보나치 수1 [JAVA]

문제 해석

• 이 문제는 피보나치 수를 구하는 방식으로 재귀 방식 OR 동적 프로그래밍 방식 중 어떠한 것이 좀 더 빠른지에 대해 알아보는 문제이다.
• 주어진 의사코드를 이해하고, 코드화하면 된다.

코드

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

public class Main {

    static int code1Cnt,  code2Cnt; //코드1, 코드2의 실행 횟수 저장 변수

    static int[] f; //동적 프로그래밍에서 사용하는 의사코드
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n =  Integer.parseInt(br.readLine()); //입력 값(n)
        f = new int[n]; //동적 프로그래밍에서 사용하는 배열 초기화

        br.close();

        /* 카운트 변수 초기화 */
        code1Cnt = 0;
        code2Cnt = 0;

        fib(n);
        fibonacci(n);

        System.out.println(code1Cnt + " " + code2Cnt);

    }

    //피보나치 수 재귀 호출 코드
    static int fib(int n){
        if(n == 1 || n == 2){
            code1Cnt++; //1이 몇번 더해졌는지 구하면 되기 떄문에 if문 안에
            return 1;
        }
        else return (fib(n-1) + fib(n-2));
    }

    //피보나치 수 동적 프로그래밍 코드
    static int fibonacci(int n){
        f[0] = 1;
        f[1] = 1;

        for(int i = 2; i < n; i++){
            //for문의 반복 횟수가 속도를 결정
            code2Cnt++;
            f[i] = f[i-1] + f[i-2];
        }
        return f[n-1]; //배열은 0부터 시작하므로
    }

}

결과

느낀 점

• 정답을 주고 풀라고 만든 문제이므로 어려운 것은 없는 문제이다.
• 하지만, 이 문제를 통해 이 경우 동적 프로그래밍이 좀 더 빠르겠구나를 확실히 볼 수 있었다. 재귀같은 경우는 피보나치 수의 경우의 수만큼 실행(n이라고 가정)하였지만 동적 프로그래밍은 n-2번 실행한 것을 볼 수 있었다.