피보나치 알고리즘

피보나치

피보나치수열은 제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다.

16 번째 항까지만 나열해 보자면 (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 이렇게 간다.

피보나치의 규칙을 간단하게 자바코드로 나타내면 아래와 같다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int x = s.nextInt();
		System.out.println(fib(x));
	}
	public static int fib(int n) {
		if (n <= 1)
			return n;
		else
			return fib(n - 1) + fib(n - 2);
	}
}

위 코드는 mian함수에서 1이하의 수를 입력하면 그대로 n을 반환하여 0이면 0, 1이면 1을 반환한다.
즉 피보나치의 3번째까지는 넣은 숫자 그대로 나온다.

하지만 예를 들어 5를 넣으면 아래 그림과 같이 fib(0)부터 차례대로 수를 구해 올라온다.
그러면 fib(0)이나 fib(1)과 같은 제일 아래 단계를 구하는 절차가 반복되며 시간 낭비를 하게된다.

그래서 fib(0)과 fib(1)의 값을 미리 정해놓은 반복 알고리즘을 사용한다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int x = s.nextInt();
		System.out.println(fib(x));
	}
	public static long fib(int n) {
		long[] f = new long[91];
		f[0] = 0;
		if (n > 0) {
			f[1] = 1;
			for (int i = 2; i <= n; i++) {
				f[i] = f[i - 1] + f[i - 2];
			}
		}
		return f[n];
	}
}

위 코드는 fib(0)과 fib(1)의 값을 미리 정의해놓고 fib(2)부터 시작한다. 즉 동일항이 반복해서 계산되는것을 줄여준다.

위 코드는 피보나치수열에서 90번째수까지만 입력한다고 가정했을때로 만들었다.
만약 더 이후의 숫자를 구하고 싶으면 f[]배열 안의 숫자를 더 늘리면 된다.