본문 바로가기
코딩과 알고리즘

백준 1003 피보나치 함수 문제풀이와 해설

반응형

은근히 헷갈리는 문제이긴 했는데, 헤메다가 결국 풀이했습니다 :)

피보나치의 합계를 푸는거라면 좀 수월할텐데,

재귀호출에서 0과 1이 나오는 횟수를 풀라니 크레이에게는 좀 난해했습니다.

피보나치 수열에서 재귀호출로 계산할 때 0과 1이 연산에 들어가는 횟수인지

숫자가 클수록 기하급수적으로 늘어나더라구요.

이것 저것 고민하다가 인터넷 다른 분의 게시글도 참고하긴 했지만,

결국은 독자적으로 초고속으로 작동하도록 새로 만들었습니다.

long long 형 변수로 선언해서

60피보나치의 0과 1의 갯수까지도 계산할 수 있으며

( 79로 시도해봤었는데 숫자 범위 초과로 엉뚱한 숫자가 구해지더라구요.

혼란드린점 죄송합니다 )

60피보나치일 경우라도 연산시간은 10ms 이내인듯 합니다 :)

측정해보기는 귀찮아서 해보진 않았구요.

백준사이트는 최대값이 40인데 결과가 0ms 로 나오더라구요.

시간제한

0.25초

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.

두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.

fibonacci(0)은 0을 출력하고, 0을 리턴한다.

fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제입력

3

0

1

3

예제출력

1 0

0 1

1 2

크레이의 해설

피보나치 수열을 구하는 방법 중 가장 비효율적인 방법은

바로전단계와 전전단계의 숫자를 더해주는 것을 무한정 재귀 호출하는 방법입니다.

보통 피보나치 수열을 구하기 위해서는

통상적으로 맨 앞에 0 과 1을 써놓고, 3번째 숫자부터는 바로 앞의 2개의 숫자를 구하는 방법이 있습니다

처음에는 0 과 1을 써놓고

0 1

그 다음 칸에는 맨 뒤에 놓여진 2개의 숫자의 합을 적습니다.

0 + 1 = 1

그 다음 칸에 또 연속해서 맨 뒤에 놓여진 2개의 숫자의 합을 적는 것이지요

0 1 + 1 = 2

이 과정을 계속 반복하는 것이 바로 피보나치 수열입니다.

0 1 1 2 3 5 8 + 13 = 21 ...

위에서 21은 피보나치 몇번 수열일까요?

9번째이긴 하지만 8번 수열입니다. 피보나치 수열은 0번부터 시작하기 때문이지요 :)

이런 방식으로 피보나치 수열을 구하면 피보나치 수열은 금방 구해집니다.

하지만 본 문제는 피보나치 수열을 가장 비효율적으로 구하는 방법을 채택할 때의 최종 재귀호출이 되는 피보나치함수0번1번이 각각 몇번씩 호출되는지를 구하는 문제입니다.

한번 피보나치 6번 수열을 기준으로 들어볼까요?

피보나치 6번은 피보나치 5번 + 피보나치 4번입니다.

결과론적으로는 8 = 5 + 3 이지만, 피보나치 5번함수가 값이 5라는 사실과 피보나치 4번이 값이 3이라는 사실은 아직 알수가 없습니다.

다시 피보나치 5번 함수의 결과를 알기 위해 피보나치5번 = 피보나치4번 + 피보나치3번을 구합니다. 이 과정을 1또는 0이 확정될때까지 구하는 것입니다.

전체 연산 과정을 살펴보도록 할까요?

피보나치6번 이렇게 적으면 너무 기니까 P(6)으로 적어보도록 할까요?

P(6)=P(5)+P(4)

P(5)=P(4)+P(3)

P(4)=P(3)+P(2)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(2)=P(1)+P(0)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(4)=P(3)+P(2)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(2)=P(1)+P(0)

빨간색으로 표시된 부분이 피보나치 0번, 1번이 사용되는 횟수인데

P(0)은 5번, P(1)은 8번 사용되었지요?

원래 간단한 계산인데 매우 복잡해졌습니다.

이 문제의 목적은 이 횟수를 구하는 것입니다.

그러면 그냥 원래의 재귀함수를 이용해서 세면서 구하면 되지 않느냐는 생각이 있을 수 있지만,

결론을 말씀드리면 그 방법으로는 문제를 해결할 수 없습니다.

왜냐하면 피보나치 숫자가 커지면 커질수록 횟수가 기하급수적으로 불어나기 때문입니다.

문제에서 제시된 최대값 피보나치40의 경우

0은 63,245,986, 1은 102,334,155 번 사용됩니다.

시도해본 결과 본 문제의 제한시간 0.25내에 통과해야 하는데 통과할 수 없습니다.

그렇다면 어떤 방법이 있을까요?

가장 효율적인 방법은 반복적인 계산을 없애는 것입니다.

피보나치에서 사용되었던 0과 1의 사용횟수를 저장했다가 활용하는 방법이지요.

그러려면 각 결과값을 저장할 변수를 먼저 전역변수로 선언해야 합니다.

원래 41이면 되지만 크레이는 테스트할게 있어서 101까지 선언했지요 :)

 

// 0~40번까지 0과 1과 합계를 담을 변수 정의
long countarr_0[41];
long countarr_1[41];
long sumarr[41];

테스트 케이스를 입력받아 반복하는 부분은 아주 기초단계이므로 넘어가도록 하겠습니다 :)

제일 먼저 시작하기 전에 전역변수를 모두 0으로 초기화해줍니다.

 

		for(int i=0;i<=40;++i)
		{
			countarr_0[i]=0;
			countarr_1[i]=0;
			sumarr[i]=0;
		}

다음 단계로 입력받은 숫자의 피보나치함수를 바로 호출하는 것이 아니라,

0부터 시작해서 1씩 숫자를 올려가며 피보나치 함수를 호출합니다.

		for(int i=0;i<=n;++i)
			fibonacci(i, i);

피보나치 함수는 이렇게 생겼습니다.

어떤 결과가 나올까요?

 

// 피보나치 함수에 현재 구하려는 수를 함께 넘긴다
int fibonacci(int n, int base) 
{
	if(sumarr[n]>0)return sumarr[n];
    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }
    else {
		int sum1, sum2;
		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}
		else sum1=fibonacci(n-1, base);

		if(sumarr[n-2]>0)
		{
			sum2=sumarr[n-2];
			countarr_0[base]+=countarr_0[n-2];
			countarr_1[base]+=countarr_1[n-2];
		}
		else sum2=fibonacci(n-2, base);

		//printf("%d = %d + %d\n", n, n-1, n-2);
		return sumarr[base] = sum1 + sum2;
    }
}

피보나치 함수를 호출하는 전체횟수가 매우 단축되는데요.

기하급수적으로 늘어나지 않고 n + 3번만 호출됩니다.

0부터 시작해볼까요? 먼저 피보나치 0을 구합니다.

fibonacci(0, 0);

그러면 함수의 흐름에 따라 P(0)이 한번 사용되었다고 0번 배열에 저장하고 끝납니다.

 

    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }

다음으로 피보나치 1을 구합니다. 0과 비슷한 방식으로 P(1)이 한번 사용되었다는 표식으로 1번 배열에 저장하고 끝납니다.

 

    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }

다음으로 피보나치 2를 구하는데요.

이 때부터는 좀 생각을 해야 합니다.

n과 base 라는 변수 2개가 주어지는 이유가 있기 때문입니다.

 

fibonacci(int n, int base) 

n은 현재의 재귀호출되는 피보나치 수열번호이고,

base는 처음의 피보나치 수열번호입니다.

이를테면 P(2)를 구할때는

다시 P(1), P(0)을 호출하게 되는데,

P(1) 과 P(0) 을 호출할 때 n값은 각각 1과 0이지만,

base 값은 처음 숫자인 2인 것이지요.

그러면 피보나치 함수 내에서는 앞에서 처리되었던 동일한 코드를 거치지만,

다른 결과를 낳습니다.

각각 countarr_0 배열변수와 countarr_1 배열변수에서

0, 1번 배열이 아닌 2번 배열에 사용횟수를 더해주게 됩니다.

 

    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }

그리고 추가적으로 P(1) + P(0)계산이 끝난 다음,

sumarr[2] 번 변수에 합계값을 저장합니다.

합계를 구하는 부분은 사실 필요없지만,

이미 0과 1의 갯수를 세었다는 표시로 저장해놓는 것이지요.

return sumarr[base] = sum1 + sum2;

이제 다시 피보나치 3번을 구해볼까요?

P(3) = P(2) + P(1) 입니다.

P(1) 은 바로 전과 똑같지만

P(2) 는 좀 다릅니다. 이 때부터 고속 산출 방식이 적용되는데요.

이미 P(2)의 0과 1의 사용횟수와 합계는 계산이 끝났기 때문에

계산이 끝난 값을 사용하면 됩니다.

n의 값은 현재 3입니다. P(2) 의 합계값인 sumarr[n-1] 변수에 합계가 저장되어 있습니다.

그러니 0과 1의 사용횟수도 저장된 횟수를 불러다가 3번 배열에 저장해주는 것이지요.

		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}

피보나치 3번의 합계 또한 산출했다고 저장해놓습니다.

 

return sumarr[base] = sum1 + sum2;

피보나치 4번에서는 어떨까요?

P(3) + P(2) 인데, 이번에는 2개 모두 이미 계산이 끝난 상황이기 때문에

위와 동일한 로직에 따라,

P(3)의 0과 1의 사용횟수, P(2) 의 0과 1의 사용횟수를 더해서 4번째 사용횟수와 합계 배열에 저장합니다.

이 과정을 목적이 되는 숫자까지 계속 반복하는 것입니다.

결론을 말씀드리면 재귀호출로 구할 수밖에 없었던 0과 1의 사용횟수, 합계를 전역변수에 저장하여 반복계산을 하지 않음으로서 재귀호출과정이 현저하게 줄어드는 방식입니다.

꽤 머리를 굴려야 해서 이론적인 부분의 설명은 이 것으로 마치고,

실제 구현된 부분은 아래 소스 코드를 통해서 이해해 주시기 바랍니다.

이런 유형의 문제풀이는 여러번 봐서 눈에 익히고 한번 직접 풀어보셔야

이해가 가능하니 한번에 이해가 안된다고 낙담하지 마세요 :)

소스

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

// 0~40번까지 0과 1과 합계를 담을 변수 정의
long long countarr_0[101];
long long countarr_1[101];
long long sumarr[101];

// 피보나치 함수에 현재 구하려는 수를 함께 넘긴다
int fibonacci(int n, int base) 
{
	if(sumarr[n]>0)return sumarr[n];
    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }
    else {
		int sum1, sum2;
		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}
		else sum1=fibonacci(n-1, base);

		if(sumarr[n-2]>0)
		{
			sum2=sumarr[n-2];
			countarr_0[base]+=countarr_0[n-2];
			countarr_1[base]+=countarr_1[n-2];
		}
		else sum2=fibonacci(n-2, base);

		//printf("%d = %d + %d\n", n, n-1, n-2);
		return sumarr[base] = sum1 + sum2;
    }
}

void Result()
{
	int t;

	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		for(int i=0;i<=40;++i)
		{
			countarr_0[i]=0;
			countarr_1[i]=0;
			sumarr[i]=0;
		}
		for(int i=0;i<=n;++i)
			fibonacci(i, i);

		printf("%lld %lld\n", 
			countarr_0[n],
			countarr_1[n]);
	}
}
int main()
{
       Result();
      return 0;
}

 

반응형