[JAVA, 피보나치 알고리즘] 피보나치 코드 구현의 다양한 방법

DP의 대표격인 피보나치 알고리즘.

이를 구현하는 데에는 다양한 방법이 존재한다.

그 중 몇가지를 소개하고자 한다.

---

1. 재귀함수

import java.util.*;
import java.io.*;


public class fibo {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		System.out.println(fibo(num));

	}

	
	public static int fibo(int n) {
		
		if(n <= 1) {
			return n; 
		}else {
			return fibo(n-2) + fibo(n - 1);
		}
		
	}
}

 

---

 

2. 동적프로그래밍 기법으로 구현(DP)

- DP에 대한 설명은 아래 URL을 참고하도록 하자 https://dnf-lover.tistory.com/13

import java.util.*;
import java.io.*;


public class fibo {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		System.out.println(fibo(num));

	}

	
	public static int fibo(int n) {
		
		int[] result = new int[n + 1];
		
		for(int i = 0; i <= n; i++) {
			if(i <= 1) {
				result[i] = i;
			}else {
				result[i] = result[i - 2] + result[i - 1];
			}
		}
		
		return result[n];
		
	}
}