[Unity C#] 피보나치 수열(재귀,메모이제이션)

개념

과정

참고 : marobiana.tistory.com/80

재귀 호출 과정이 생각보다 복잡해서 이미지 메이킹이 어려운데 해당 포스팅에서 쉽게 설명해주고 있다.

 

일반 재귀 vs 메모이제이션 재귀

피보나치 구현 시, 일반 재귀 코드는 문제가 있다. 이미 계산한 내용을 또 다시 계산을 하기 때문에 필요없는 연산이 생긴다.

 

예를들어,

n = 5 일때,

fibo(1)

fibo(2)

fibo(1) + fibo(2)

fibo(2) + (fibo(1) + fibo(2))

(fibo(1) + fibo(2)) + (fibo(2) + (fibo(1) + fibo(2)))

위와 같이 전에 계산한 값을 매번 다시 계산을 한다.

 

n이 매우 커질 경우

오버헤드가 너무 크다.

 

실제로 n = 30을 넣어보면,

결과가 안나오거나 느리게 나오는 것을 알 수 있다.

계속 계산을 수행하고 있지만, 연산량이 너무 많아서 그렇다.

 

이때, 메모이제이션 방법을 사용한다!

이미 계산한 내용들을 저장해두고,

다시 연산 할 필요없이 저장된 데이터를 불러오는것이다.

 

data[1] = fibo(1)

data[2] = fibo(2)

data[3] = data[1] + data[2] = fibo(3)

data[4] = data[2] + data[3] = fibo(4)

data[5] = data[3] + data[4] = fibo(5)

 

공간을 조금 더 사용해서 데이터를 저장해두면(기억을 하면)

연산량을 대폭 줄일 수 있다.

메모제이션을 안쓰면, 시간복잡도는 O(2^N)이다.

n이 커질수록 어마어마하게 시간이 오래걸린다는것을 알 수 있다.

하지만, 메모제이션 방법을 사용하면 시간복잡도는 O(N)으로 급격히 줄어든다.

출처: https://hongku.tistory.com/161

소스코드 - 재귀

public class Fibo_Source : MonoBehaviour
{
    void Start()
    {
        int input = 5;

        for(int i = 1; i <= input; i++)
        {
            Debug.Log(fibonacci(i));
        }
    }

    int fibonacci(int n)
    {
        if( n <= 1)
        {
            return n;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

소스코드 -재귀 + 메모이제이션

public class FiboMemoization_Source : MonoBehaviour
{
    int[] data = new int[100];
    void Start()
    {
        int input = 5;

        for (int i = 1; i <= input; i++)
        {
            Debug.Log(fibonacci(i));
        }
    }

    int fibonacci(int n)
    {
        if(n <= 1)
        {
            return n;
        }

        if(data[n] != 0) // 해당 인덱스 값이 0이 아니다 == 이미 계산해서 값이 있음
        {
            return data[n];
        }
        else // 해당 인덱스 값이 0이다 == 값이 없다 피보나치 연산
        {
            data[n] = fibonacci(n - 1) + fibonacci(n - 2); 

            return data[n];
            //data[2] = 1 + 0 = 1
            //data[3] = data[2] + 1 = 2
            //data[4] = data[3] + data[2] = 3
            //data[5] = data[4] + data[3] = 5
        }
    }
}

출력

1 1 2 3 5

재귀 연습겸 팩토리얼 소스코드

public class Factorial_Source : MonoBehaviour
{
    void Start()
    {
        Debug.Log(Factorial(5)); // 5+4+3+2+1 = 15
    }

    int Factorial(int n)
    {
        if (n < 1)
        {
            return 0;
        }

        return n + Factorial(n-1);
        // 5 + {Factoral(5-1):return 10} = 15
        // 4 + {Factoral(4-1):return 6} = 10
        // 3 + {Factoral(3-1):return 3} = 6
        // 2 + {Factoral(2-1):return 1} = 3
        // 1 + 종료
        //아래서부터 위로 생각
    }
}