24416번_알고리즘 수업 - 피보나치 수 1_java

● 정리

• 재귀

public static int fib_recursion(int n) {
	cnt++;
	if(n == 1 || n == 2) {
		return 1;
	} else {
		return fib_recursion(n-1) + fib_recursion(n-2);
	}
	
}

자기자신을 반복해서 호출   
f(n)을 구하기 위해 f(n-1), f(n-2)를 구하고 f(n-1), f(n-2)는 다시 쪼개지면서 f를 다시 호출하지 않을때까지 반복하는 방식(하향식)   
fib(5) = fib(4) + fib(3)   
　　　= fib(3) + fib(2) + fib(3) = fib(2) + fib(1) + fib(2) + fib(2) + fib(1)   
　　　= 3 * fib(2) + 2 * fib(1)   
fib(4) = fib(3) + fib(2)   
fib(3) = fib(2) + fib(1)   
n=5 일 경우 함수 호출 9번 발생   
n=30 일 경우 함수 1664079번 호출 

• DP(Dynamic Programming)

public static int fib_dp(int n) {
	int[] dp = new int[n+1];
	
	dp[1] = 1;
	dp[2] = 1;
	
	for(int i=3; i<=n; i++) {
		cnt++;
		dp[i] = dp[i-1] + dp[i-2];
	}
	
	return dp[n];
}

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해서 동일한 계산의 반복 수행을 제거하는 방법   
1부터 n까지 올라가면서 각 단계의 값을 메모리에 저장해서 다음 단계의 값을 구할때 사용(상향식)   
dp[3] = dp[2] + dp[1] = 1 + 1 = 2   
dp[4] = dp[3] + dp[2] = 2 + 1 = 3   
dp[5] = dp[4] + dp[3] = 3 + 2 = 5   
n=5 일 경우 for문 3번 반복   
n=30 일 경우 for문 28 반복 

● 코드

package acmicpc;

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

public class acmicpc24416 {
	static int cnt = 0;
	public static void main(String[] agrs) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
			
			int n = Integer.parseInt(reader.readLine());
			
			fib_recursion(n);
			writer.append(String.valueOf(cnt) + " ");
			cnt=0;
			fib_dp(n);
			writer.append(String.valueOf(cnt));
			
			writer.flush();
			writer.close();
		} catch (Exception e) {
			
		}
	}
	
	public static int fib_recursion(int n) {
		if(n == 1 || n == 2) {
			cnt++;
			return 1;
		} else {
			return fib_recursion(n-1) + fib_recursion(n-2);
		}
		
	}
	
	public static int fib_dp(int n) {
		int[] dp = new int[n+1];
		
		dp[1] = 1;
		dp[2] = 1;
		
		for(int i=3; i<=n; i++) {
			cnt++;
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		return dp[n];
	}
}