(알고리즘)피보나치 수열

피보나치 수열은 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배열을 말한다.

수식으로는 f(n) = f(n - 1) + f(n - 2)

0, 1, 1, 2, 3, 5, 8, 13, …

 

ex)

 

 

피보나치 수열을 푸는 방법에는 3가지가 있다.

1. 재귀
2. 반복
3. 배열

 

1. 재귀

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

 

2. 반복

public static int finonacci(int n) {
	int a = 0;
	int b = 1;
	int c = 0;
	
	for (int i = 1; i <= n; i++  {
		c = a + b;
		a = b;
		b = c;
	}

	return c;
}

 

3. 배열

public static int fibonacci(int n) {
	int[] dp = new int[n + 1];

	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return dp[n];
}

 

 

코딩테스트 문제를 푸는데 생각보다 사용되는 경우가 많으니 알면 좋다.