팩토리얼 (Factorial)

목차 

1. 팩토리얼이란?

2. 순환을 이용한 팩토리얼

3. 반복을 이용한 팩토리얼

 

 

 

1. 팩토리얼이란?

특정 정수에서 1까지의 수를 모두 곱하는 것을 뜻합니다. 기호는 숫자 뒤에 느낌표인 !를 붙입니다.

예를 들어,  4! = 4 x 3 x 2 x 1 입니다. 즉, 4! = 24입니다.

마찬가지로 5! 는 5 x 4 x 3 x 2 x 1  = 120입니다.

 

 

2. 순환을 이용한 팩토리얼

위에서 말했듯이 팩토리얼은 다음과 같습니다.

4! =       4 x 3 x 2 x 1

5! =  5 x 4 x 3 x 2 x 1

위와같이 배치해보니 4! 에 5만 곱하면 5! 가 되는것을 알수 있습니다. 즉, 5! = 5 x 4! 가 되는 것입니다.

5를 임의의 수 n 으로 나타내보면 n! = n x (n-1)! 인 형태인 것을 볼수 있습니다.

즉 하나의 팩토리얼 함수를 순환적으로 호출하다보면 값이 나오는 것입니다.

 

#include <stdio.h>

int factorial_recursive(int num)	//recursive 는 '순환적인'이라는 뜻입니다.
{

    if (num <= 1) return 1;			// 1! = 1
    return num * factorial_recursive(num-1);	// n! = n * (n-1)!
    
}

int main() {

	//순환을 이용한 팩토리얼
    printf("%d",factorial_recursive(4));	// 4!
    printf("\n");				// 줄 바꿈
    printf("%d",factorial_recursive(5));	// 5!

    return 0;
}

 

결과 :

24

120

 

[시간복잡도]

순환적인 팩토리얼을 점화식으로 나타내면 T(n) = T(n-1) + c 입니다. c 는 n 과 factorial_recursive(n-1) 를 곱하는 비용입니다.

순환을 수행할때마다 알고리즘이 수행해야할 크기가 n 에서 n-1 로 줄어드므로 시간복잡도는 O(n) 입니다.

 

 

3. 반복을 이용한 팩토리얼

#include <stdio.h>


int factorial_iterative(int num)    //iterative 는 '반복적인'이라는 뜻입니다.
{
    if(num <= 1) return 1;          // 0! = 1 이고 1! = 1 이기 때문에 인수가 1 이하이면 바로 1을 
                                    // 리턴해준다
    
    int result = 1;                 //결과값을 나타낼 result
    
    for(int i = 2; i <= num; i++)   //2부터 시작하여 num 이하까지의 수를 곱한다.
        result *= i;
    
    return result;                  //리턴 결과가 곧 num!이다
}

int main() {
    
    //반복을 이용한 팩토리얼
    printf("%d",factorial_iterative(4)); // 4!
    printf("\n");                        // 줄 바꿈
    printf("%d",factorial_iterative(5)); // 5!
    
    return 0;
}

 

 

결과 :

24

120

 

[시간복잡도]

반복문이 n-1 번 반복하니 시간복잡도는 O(n) 입니다. 순환적인 방법과 시간복잡도가 같습니다.