피보나치 수열

피보나치수열을 알면 1분컷 모르면 난이도 헬이 되는 문제들이 많죠

피보나치 수열 문제는 구현이 어렵지 않습니다.
이 문제를 피보나치로 풀 수 있느냐 아니냐를 판단할 수 있는 능력이 더욱 중요할 것 같습니다.

 

시작!

 

1. 피보나치 수열

피보나치는 f(n) = f(n-1) + f(n-2) 라는 공식을 갖는 수열입니다.

f(1) = 1, f(2) = 1 이라고 가정하게 되면 수열은 아래와 같이 진행됩니다.

1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55 -> 89 -> 144 .....

대표적으로 타일링 문제가 피보나치 수열을 사용하는 문제 중 하나죠.

피보나치를 구현하는 방법은 다양합니다만 오늘 다룰 방식은 1)재귀함수 방식, 2)for문을 이용한 방식
이렇게 2가지로 구현하여 정리 해 볼 예정입니다.

 

2. 재귀함수를 이용하여 피보나치 수열 구현하기

public int fibo_Recursive(int num) {
		//1,1,2,3,5,8,13,21,34,55,89,143 ...
		if(num == 1) {return 1;}
		else if(num == 2) {return 1;}
		else
			return fibo_Recursive(num-2) + fibo_Recursive(num-1);
	}

코드는 간단합니다.

그럼 피포나치 수열 중 6번째 수를 구하는 과정을 보도록 하겠습니다. (1, 1, 2, 3, 5, 8 ...)

그림 1. 피보나치 순환 구조

 

6번째 값을 구하는 과정을 보면 위 그림과 같이  f(5) -> f(4) -> f(3) -> f(2),f(1) 순서로 함수를 호출하며 값을 더해 갑니다.

그런데 이 경우 구현은 쉽지만 재귀함수 특성상 메모리를 많이 사용하기 때문에 코딩테스트에서 사용하기엔 적합하지 않습니다.

그래서 두 번째 방법 반복문을 이용하여 피보나치를 구현하는 것 입니다.

 

2. 반복문을 이용하여 피보나치 수열 구현하기

코드를 먼저 보도록 하겠습니다.

public int fobo_loop(int num) {
		int cur = 1;  // 현재 값
		int next = 1; // 다음 값
		int answer = 0; // 합을 저장할 변수
		
		for(int i=1; i<=num; i++) {
			cur = next;
			next = answer;
			answer = next + cur;
		}
		return answer;
	}

 

for문으로 구현할 경우
1) 현재 값을 저장할 변수 cur 다음 값을 저장할 next, 그리고 두개의 합을 저장할 변수 answer을 생성하고
2) 첫째항부터 원하는 위치까지 하나씩 더하는 과정을 반복 합니다.

6번째 항을 구하는 과정을 그림으로 봅시다.

그림 2. 피보나치 수열 반복문 구조

그림에서 보듯이 첫째 항 : cur = 1,  둘째 항 : next = 2로 두고, 이 두개를 더한 값을 answer에 저장합니다.
처음에 6번째 수를 구하고자 하였으니 6번을 반복하게 되면 원하는 값인 8이 출력되게 됩니다.

반복문으로 구현하게 되면 기대 되는 시간 복잡도는 O(n)이 되기 때문에  재귀함수에 비해 효율적으로 사용할 수 있어 코딩테스트를 할때 사용하기 편리합니다.

 

이상!