#24416 : 알고리즘 수업 - 피보나치 수 1

풀이방법

사용된 것:

재귀

DP (동적 프로그래밍)

 

 

 

 

 

2023.04.05

재귀는 함수를 정의하여 구현하였다.

 

DP는 main 메소드 안에 반복문을 적어 구현하였다.

단, 피보나치의 특성상 DP를 수행하지 않고 주어진 n에서 2를 뺀 수를 출력해도 정답이다.

 

정수형 변수 a에 재귀함수의 수행횟수를 저장하고,

정수형 변수 b에 DP의 수행횟수를 저장하였다.

 

재귀의 경우, 최초에 함수를 한 번 실행하면서 실행하므로 일단 a에 1을 더하고 시작하였다.

그 후, 함수 안에서 재귀를 한 번 할 때마다 a를 1씩 증가시켰다.

 

DP의 경우,

덧셈이 한 번 수행될 때마다 b를 1씩 증가시켰다.

 

 

코드

Java(2023.04.05)

import java.util.Scanner;

public class Main {
	
	static int a;	// 재귀 방식을 사용했을 때의 코드 실행 횟수를 저장할 변수
	static int b;	// DP 방식을 사용했을 때의 코드 실행 횟수를 저장할 변수
	static Integer[] dp;	// DP의 메모이제이션을 위한 저장공간(정수 배열) 선언

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner (System.in);
		
		Integer n = sc.nextInt();
		
		// 정답 변수를 0으로 초기화
		a = 0;
		b = 0;
		
		// 재귀 방식을 사용했을 때의 함수 수행 횟수 구하기
		a++;	// 최초 fib(n) 호출도 카운트해주어야 하므로 1을 더하고 시작
		fib(n);
		
		// 메모이제이션을 위한 배열 생성
		dp = new Integer[41];
		// 첫 번째 & 두 번째 피보나치 수를 1로 설정
		dp[1] = 1;
		dp[2] = 1;
		
		// 반복문으로 DP 실행
		if (n == 1 || n == 2) b = 0;
		else {
			for (int i=3; i<=n; i++) {
				b++;
				dp[i] = dp[i-1] + dp[i-2];
			}
		}
		
		//정답 출력
		System.out.print(a + " " + b);		
		
		sc.close();

	}
	
	// 재귀 방식의 피보나치 함수
	public static Integer fib(int n) {
		if(n == 1 || n == 2) return 1;	// base case에서는 fib() 재귀호출이 일어나지 않으므로 a를 증가시키지 않음
		else {
			// n이 3 이상일 때에는 재귀호출이 일어나므로 a를 증가시킴
			a++;
			return fib(n-1) + fib(n-2);
		}
	}
	

}