피보나치 수열 구현하기

피보나치 수열이란

[이미지 출처- Samsung display newsroom]

 

수열이란 어떠한 공통된 규칙을 가진 숫자들의 열을 말한다.

피보나치수열은 위 그림과 같이

n번째 수 = (n-1)번째 수 + (n-2)번째 수

 

형태의 규칙을 가지는 수열이다.

(단, n=1or n=0 일때 1이며 위의 식은 n>=2부터 적용됨.)

 

 

 

 

 

그럼 이 수열은 코드로 어떻게 구현할 수 있을까.

아래의 문제를 풀어보자.

 

Q. 입력받는 숫자 하나가 수열의 인덱스값을 나타낸다고 가정할때, 해당 인덱스가 가리키는 값을 출력하는 코드를 만드시오.

 

ex)

입력: 5

출력: 8

 

입력:1

출력:1

 

입력:234

출력:57239589

 

 

1. while문을 통한 구현

 

 

 

 

2. 출력값을 리턴하는 함수 만들어서 구현 (fibo함수 만들기)

 

#include <iostream>

using namespace std;

int fibo(int num)
{
	if (num <= 1)
	{
		return 1;
	}

	return fibo(num - 2) + fibo(num - 1); //원래 이 리턴값을 무조건 튀어나오게 하는 함수 
}

int main()
{
	int num;
	cin >> num;

	cout<< fibo(num);

	return 0;
}

 

fibo라는 함수를 만들어서 일정한 형태 fibo(num - 2) + fibo(num - 1) 를 리턴해줌으로서 피보나치 수열을 구현하는 방식이다.

 

이 코드의 문제점이 존재한다.

바로 fibo(num - 2) + fibo(num - 1) 을 실행하면 2개의 가지로 나뉘게 되어 거슬러 올라가는데,

그러다보면 중복되는 개체(가지)가 생긴다는것이다.

그래서 input값(index값)으로 큰 값을 입력하면 코드가 멈춘다....

 

이 해결 방법은 이전에 미로찾기에서 갔던 길을 다시 안 가기위해 만들었던 used함수와 같은 개념을 사용하는 방법이다.

둘로 쪼갤때마다 해당값들을 모두 memorize함수에 저장하고,(used함수와 같은기능)

이전에 이미 둘로 쪼개어 계산되었던 적이 있는 인덱스 가지정보에 대한 정보를 memorize함수에서 찾아다가  불러오는 방법이다.

이렇게 문제점을 보완한 방법이 바로 세 번째 방법이다.

 

 

3. 출력값을 리턴하는 함수+ memorize함수 (fibo함수+memorize함수)

#include <iostream>

using namespace std;

int memorize[100000] = { 0 };

int fibo(int num);

int main()
{
	int num;
	cin >> num;

	cout<< fibo(num);

	return 0;
}


int fibo(int num)
{
	if (num <= 1)
	{
		return 1; //num이 0,1일때만 1 튀어나오게 함
	}

	if (memorize[num])
	{
		return memorize[num];
	}

	return memorize[num] = fibo(num - 2) + fibo(num - 1); 

}

 

 

 

 

 

 

 

 

 

 

 

틀린 부분이나 이상한 부분이 있으면 댓글로 지적해주세요! 

감사합니다 :)