[C언어] 재귀함수(피보나치수열)는 자신을 return하면 안된다

[C언어] 재귀함수(피보나치수열)는 자신을 return하면 안된다

백준 1003번 문제인 피보나치수열(재귀함수)를 풀면서 자꾸 시간초과가 떴는데, 알고보니 자기 자신을 리턴해서 발생했던 것이었다. 이번시간에는 피보나치수열(재귀함수)에서 자기자신을 리턴해주면 안되는 이유를 포스팅하고자 한다.

 

<백준 1003번 문제(피보나치 수열) 바로가기>

 

 

 

반응형

 

---

 

1. 피보나치 수열은 무엇인가?

 

피보나치 수열이란 자기 함수안에서 자기 함수를 재귀적(Recursive)으로 불러들이는 수열을 의미한다.

 

피보나치 수열의 수학적 정의는 아래와 같다.

 

 

이런 피보나치 수열형태를 소스코드화하면 간단하게 아래와 같이 생각할 수 있다.

 

fibonacci(int n){
   //주저리 주저리..
   
   return fibonacci(n-1) + fibonacci(n-2)
}

 

 

즉, 함수안에서 자기 자신을 계속 부르고 부르는 형태로 소스를 짤 수 있다.

 

 

반응형

 

---

2. 백준1003번 소스코드로 구현하기 (시간초과로 실패!)

 

 

아래 소스코드는 백준 1003번 문제인 피보나치수열의 소스코드를 구현한 결과이다.

#include <stdio.h>

int fibonacci(int, int*, int*);

int main(){
	int T=0;
	int n=0;
	int count_0 = 0;
	int count_1 = 0;

	scanf("%d",&T); //실행할 테스트케이스 개수 설정

	for(int i=0; i < T ; i++)
	{
		printf("Put number:");
		scanf("%d", &n);
		if(n <= 40 && n >= 0)
		{
			fibonacci(n, &count_0, &count_1);
			printf("%d %d\n", count_0, count_1);
		}
		else i--;
		count_0 = 0;
		count_1 = 0;
	}
	return 0;
}

int fibonacci(int n, int *count_0, int *count_1) {
    if (n == 0) {
        //printf("0");
		(*count_0)++;
        return 0;
    } else if (n == 1) {
       //printf("1");
		(*count_1)++;
        return 1;
    } else {
        return fibonacci(n-1, count_0, count_1) + fibonacci(n-2, count_0, count_1);
    }
}

 

근데, 채점결과가 자꾸 '시간 초과'로 뜨는 것이 아닌가..

 

시간이 몇초가 걸리는지 시간체크를 해봤다(아래 코드 참고).

#include <stdio.h>
#include <time.h>

int fibonacci(int, int*, int*);

int main(){
	int T=0;
	int n=0;
	int count_0 = 0;
	int count_1 = 0;
	double stime=clock();

	//scanf("%d",&T); //실행할 테스트케이스 개수 설정

	for(int i=0; i < 1 ; i++)
	{
		printf("Put number:");
		scanf("%d", &n);
		if(n <= 40 && n >= 0)
		{
			fibonacci(n, &count_0, &count_1);
			printf("%d %d\n", count_0, count_1);
		}
		else i--;
		count_0 = 0;
		count_1 = 0;
	}
	printf("%f sec!!!!",(double)(clock()-stime)/CLOCKS_PER_SEC);
	return 0;
}

int fibonacci(int n, int *count_0, int *count_1) {
    if (n == 0) {
        //printf("0");
		(*count_0)++;
        return 0;
    } else if (n == 1) {
       //printf("1");
		(*count_1)++;
        return 1;
    } else {
        return fibonacci(n-1, count_0, count_1) + fibonacci(n-2, count_0, count_1);
    }
}

 

가장 큰 수인 40을 넣고 소스코드를 돌려보니.. 무려 2.4초나 걸리는 것이 아닌가!!

자연수 40으로 피보나치 걸린 시간

 

 

백준 1003번 문제의 ' 0.25 초 (추가 시간 없음)' 시간제한 요구도를 충족시키지 못하는 주요 이유는 피보나치수열을 구현하면서 사용했던 자기자신을 return하면서 발생했던 것이었다.

 

반응형

 

---

3. 피보나치 수열(재귀함수)에서 자기자신을 return하면 안되는 이유

 

최종 값을 리턴하기 전까지의 데이터는 스택(Stack) 메모리에 저장된다. 스택 영역은 프로그램이 자동으로 사용하는 임시 메모리 영역이다. 함수 호출 시 생성되는 지역 변수와 매개 변수가 저장되는 영역이고, 함수 호출이 완료되면 사라진다.

 

이러한 임시 영역에 대량의 데이터를 쌓다보니 재귀함수처럼 함수 안에 함수를 넣게 되면 엄청난 시스템의 부하를 일으키고 Stack Overflow를 야기시킬 수 있다.

 

일례로, 백준에서 제공하는 요구도인 40을 피보나치수열로 돌리게 되면,  2^40의 계산을 수행해야 한다. 2의 40승은 1조 정도의 큰 수다. 이것은 컴퓨터 메모리에 저장하기에도 상당한 양의 공간이 필요하며, 정수 데이터 타입의 범위를 초과하는 큰 수다. 이를 우리는 '시간복잡도'라고 하며, 피보나치 수열은 o(n^2)의 시간복잡도를 갖는다고 표현한다.

따라서, 이렇게 함수안에 자기자신을 Return하여 뺑뺑 돌리는 코드는 임시로 값 확인용으로 써야지, 공식 버전에 갖다 쓰면 큰 문제를 일으키므로 조심해야 한다!!!

 

회사에서 절대 쓰지 말길 바란다!!

 

반응형

 

---

4. 동적 프로그래밍(DP)과 메모이제이션

 

이러한 피보나치 수열의 O(n^2)의 시간복잡도를 낮출 수 있는 트릭이 있다.

바로 이전 스텝에서 썼던 결과값들을 Stack메모리가 아닌 영구 메모리에 저장해두고 필요할 때 다시 사용하는 것이다.

이런 기법을 메모이제이션(memoization)이라고 한다. 메모이제이션은 동적 프로그래밍(DP)의 한 종류로, 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법론이다. 쉽게 말해, DP는 '기억하며 풀기' 인 셈이다.

 

아래는 메모이제이션의 간단한 예시이다. 

long long fib(int n) { 
long long a[100] = { 0, 1, };
if (n < 2 || a[n] != 0) { // 해당 피보나치 수를 이미 구한 경우
return a[n];
}

else { // 피보나치 수를 아직 구하지 않은 경우
a[n] = fib(n - 1) + fib(n - 2);
return a[n];
}
}

위 방법의 시간복잡도를 구해보면 

T(0) = 1, T(1) = 1이고

T(2) = T(1) + T(0) + 1 = 3

T(3) = T(2) + T(1) + 1 = 5

T(4) = T(3) + T(2) + 1에서 T(2)는 저장한 피보나치 수를 가져오기만 하면 되기 때문에 T(2) = 1이다. 따라서 T(3) + T(2) + 1 = 7이고, 같은 이유로 T(5) = T(4) + T(3) + 1에서 T(3) = 1이므로 T(5) = 9이다. 따라서 T(n) = 2n - 1이라고 할 수 있고, 시간복잡도는 O(n)가 되는 것이다.

반응형

 

---

5. 메모이제이션을 이용하여 백준 1003번 풀기

 

앞서 말했다시피, 함수가 자기 자신을 불러오는 방식은 스택 영역의 메모리 버퍼를 엄청나게 차지하기 때문에 좋은 방법이 아니라고 했다. 이를 해결하기 위해서, memo라는 배열에 이전 결과값들을 저장해놓고, 조건이 맞으면 memo 배열에서 값을 가져와서 그대로 리턴하는 방식을 수행하게 되면, O(2^n)의 복잡도를 O(n)으로 줄일 수 있다.

 

<C언어로 코드를 구현한 것>

#include <stdio.h>

void fibonacci(int n, int *memo_0, int *memo_1) {
    int max_n = 40;  // n의 최댓값
    if (n > max_n) {
        n = max_n;
    }

    int i;
    memo_0[0] = 1;
    memo_1[0] = 0;

    if (n > 0) {
        memo_0[1] = 0;
        memo_1[1] = 1;
    }

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

int main() {
    int T;  // 테스트 케이스 개수
    scanf("%d", &T);

    for (int t = 0; t < T; t++) {
        int n;  // N 입력
        scanf("%d", &n);

        int memo_0[41];  // 최댓값 n = 40을 고려하여 크기 설정
        int memo_1[41];

        fibonacci(n, memo_0, memo_1);

        printf("%d %d\n", memo_0[n], memo_1[n]);
    }

    return 0;
}

반응형

 

 

<파이썬으로 코드를 구현한 것>

def fibonacci(n):
    max_n = 40  # n의 최댓값
    if n > max_n:
        n = max_n

    memo_0 = [0] * (n + 1)
    memo_1 = [0] * (n + 1)

    memo_0[0] = 1
    memo_1[0] = 0

    if n > 0:
        memo_0[1] = 0
        memo_1[1] = 1

    for i in range(2, n + 1):
        memo_0[i] = memo_0[i - 1] + memo_0[i - 2]
        memo_1[i] = memo_1[i - 1] + memo_1[i - 2]

    return memo_0[n], memo_1[n]

T = int(input())  # 테스트 케이스 개수

for _ in range(T):
    n = int(input())  # N 입력
    result = fibonacci(n)
    print(result[0], result[1])

 

코드는 둘 다 잘 작동하고, 결과도 정상적이다.

반응형

---