백준 24416번: 알고리즘 수업 - 피보나치 수1

문제

n 개의 피보나치 수를 재귀 호출과 동적 프로그래밍으로 구하는 알고리즘의 실행 횟수 구하기

이때 아래의 의사 코드를 사용하여 피보나치 수의 실행 횟수를 구한다.

입력

첫째 줄에 입력 받는 n은 5≤n≤40으로 제한한다.

---

의사코드

피보나치 수 재귀 호출 의사 코드

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

피보나치 수 동적 프로그래밍 의사 코드

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

---

작성 코드

import java.util.Scanner;

public class Main {
	//1은 재귀함수 2는 동적 프로그래밍 함수
	static int count1=0;
	static int count2=0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//입력 제한조건 확인
		if(5<=n && n<=40) {
			fib(n);
			fibonacci(n);
			System.out.print(count1+" "+count2);
		}
	}
	
	//재귀함수
	public static int fib(int n) {
		if(n == 1 || n == 2) {
			count1++;
			return 1;
		}else
			return (fib(n-1)+fib(n-2));
		
	}
	//동적 프로그래밍 함수
	public static int fibonacci(int n) {
		int[] f=new int[n];
		f[1]=1;
		f[0]=f[1];
		
		for(int i=2;i<n;i++) {
			count2++;
			f[i]=f[i-1]+f[i-2];
		}
		return f[n-1];
	}
}

---

결과

---

동적 프로그래밍

동적 프로그래밍(Dynamic Programming, DP)은 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 그 결과를 저장하였다가 다시 큰 문제를 해결할 때 사용하는 것으로 특정 알고리즘이 아닌 하나의 문제를 해결하기 위한 패러다임으로 볼 수 있다.

큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하기 때문에 DP를 ‘기억하며 풀기’라고도 부른다.

재귀함수

재귀 함수는 정의 단계에서 자신을 재참조하는 함수를 말한다. 이러한 재귀 함수는 자신의 로직을 내부적으로 반복하다가 일정한 조건이 만족되면 함수를 이탈해 결과를 도출한다.