코테 - 팩토리얼 계산 5가지 방법

팩토리얼은 수학에서 자주 등장하는 연산으로, 코딩테스트에서도 단골 문제입니다. 이번 포스트에서는 C언어를 사용해 팩토리얼을 계산하는 5가지 방법을 소개합니다. 각 방법은 성능과 코드 구조 면에서 차이가 있으니, 상황에 맞게 활용해보세요!

1. 반복문(Iterative) 방식

가장 직관적인 방법으로, 루프를 사용해 1부터 n까지 곱합니다. 메모리 효율이 좋고 스택 오버플로우 위험이 없습니다.

#include <stdio.h>

unsigned long long factorial_iterative(int n) {
    unsigned long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int n = 5;
    printf("%d! = %llu\n", n, factorial_iterative(n));
    return 0;
}
        

장점: 간단하고 빠름.
단점: 큰 숫자에서 오버플로우 가능성.

2. 재귀(Recursive) 방식

수학적 정의를 그대로 코드로 옮긴 방식입니다. n! = n × (n-1)!를 재귀 호출로 구현합니다.

#include <stdio.h>

unsigned long long factorial_recursive(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial_recursive(n - 1);
}

int main() {
    int n = 5;
    printf("%d! = %llu\n", n, factorial_recursive(n));
    return 0;
}
        

장점: 코드가 간결하고 이해하기 쉬움.
단점: 큰 n에서 스택 오버플로우 위험.

3. 동적 프로그래밍(DP) 방식

메모이제이션을 사용해 중복 계산을 피합니다. 배열에 이전 결과를 저장해 효율성을 높입니다.

#include <stdio.h>
#include <stdlib.h>

unsigned long long factorial_dp(int n) {
    unsigned long long *dp = (unsigned long long *)malloc((n + 1) * sizeof(unsigned long long));
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = i * dp[i - 1];
    }
    unsigned long long result = dp[n];
    free(dp);
    return result;
}

int main() {
    int n = 5;
    printf("%d! = %llu\n", n, factorial_dp(n));
    return 0;
}
        

장점: 메모리와 속도 최적화.
단점: 추가 메모리 사용.

4. 꼬리 재귀(Tail Recursive) 방식

재귀 호출을 최적화해 스택 사용을 최소화합니다. 누적 변수를 사용해 계산합니다.

#include <stdio.h>

unsigned long long factorial_tail_recursive(int n, unsigned long long acc) {
    if (n == 0 || n == 1) return acc;
    return factorial_tail_recursive(n - 1, n * acc);
}

unsigned long long factorial_tail(int n) {
    return factorial_tail_recursive(n, 1);
}

int main() {
    int n = 5;
    printf("%d! = %llu\n", n, factorial_tail(n));
    return 0;
}
        

장점: 일부 컴파일러에서 최적화 가능.
단점: C에서는 꼬리 재귀 최적화 미지원.

5. 룩업 테이블(Lookup Table) 방식

미리 계산된 팩토리얼 값을 배열에 저장해 조회합니다. 빠른 응답이 필요한 경우 유용합니다.

#include <stdio.h>

unsigned long long factorial_table(int n) {
    static unsigned long long table[] = {
        1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
        39916800, 479001600, 6227020800, 87178291200, 1307674368000,
        20922789888000, 355687428096000, 6402373705728000,
        121645100408832000, 2432902008176640000
    };
    if (n < 0 || n > 20) return 0; // 오버플로우 방지
    return table[n];
}

int main() {
    int n = 5;
    printf("%d! = %llu\n", n, factorial_table(n));
    return 0;
}
        

장점: 조회만 하므로 매우 빠름.
단점: 메모리 사용, 제한된 범위.

결론

각 방법은 사용 사례에 따라 적합성이 다릅니다. 코딩테스트에서는 메모리와 시간 제한을 확인한 뒤, 가장 적합한 방법을 선택하세요. 예를 들어, 입력 범위가 작다면 룩업 테이블이 유리하고, 범위가 크다면 반복문이나 동적 프로그래밍이 안전할 수 있습니다.