큰 수의 팩토리얼(계승) 계산 – 배열을 활용한 C++ 구현 방법

왜 배열이 필요한가?

컴퓨터에서 변수는 메모리의 특정 공간에 저장되며, 그 크기는 고정되어 있습니다. 그래서 15!나 20!처럼 값이 큰 수의 팩토리얼(계승)을 계산하면 결과가 변수가 담을 수 있는 범위를 초과하는 오버플로우가 발생해 엉뚱한 값이 출력됩니다. 참고로 32비트 int형은 12!(약 47억 9천만)까지만 표현할 수 있으며, 13!부터는 이미 범위를 벗어납니다.

이 문제를 해결하려면 배열을 이용해 결과를 저장해야 합니다. 배열의 각 요소에는 결과 숫자의 한 자릿수씩을 나누어 담습니다. 단, 배열에는 곱셈 연산자를 바로 적용할 수 없기 때문에, 손으로 곱셈할 때처럼 배열의 모든 자릿수에 대해 곱셈 과정을 직접 구현해야 합니다.

입력과 출력

입력:
큰 수: 50
출력:
주어진 수의 팩토리얼:
30414093201713378043612608166064768844377641568960512000000000000

알고리즘

multiply(x, multiplicand)

입력: 곱할 수 x, 배열 형태의 큰 피승수(multiplicand)

출력: 곱셈이 반영된 결과 배열

시작
    carry ← 0
    피승수의 모든 자릿수 i에 대해 반복:
        prod ← i * x + carry
        i ← prod mod 10       (마지막 한 자릿수만 저장)
        carry ← prod / 10     (올림수 계산)
    반복 끝

    carry ≠ 0인 동안 반복:
        피승수 배열 맨 뒤에 (carry mod 10) 추가
        carry ← carry / 10
    반복 끝
끝

factorial(n)

입력: 팩토리얼을 구할 수 n

출력: n의 팩토리얼 값

시작
    결과 배열 정의
    결과 배열에 1 삽입

    i ← 2부터 n까지 반복:
        multiply(i, result) 호출
    반복 끝

    결과 배열 뒤집기
    결과 반환
끝

동작 원리

핵심 아이디어는 결과를 일의 자리부터 역순으로 배열에 저장하는 것입니다. 1×2×3×…×n을 차례로 곱해 가면서, 매번 배열의 각 자릿수에 새로운 수 i를 곱합니다. 곱한 값 중 마지막 한 자릿수는 해당 위치에 남기고, 나머지는 올림수(carry)로 다음 자릿수에 넘깁니다. 모든 자릿수를 처리한 뒤에도 올림수가 남아 있다면, 이를 한 자릿수씩 잘라 배열 끝에 추가합니다. 최종적으로 배열을 뒤집으면 원래 순서의 팩토리얼 값을 얻을 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void multiply(int x, vector<int>&multiplicand) {   // 피승수에 x를 곱하는 함수
    int carry = 0;                                  // 캐리(올림수)를 0으로 초기화
    vector<int>::iterator i;

    for (i = multiplicand.begin(); i != multiplicand.end(); i++) {  // x를 피승수의 모든 자릿수와 곱함
        int prod = (*i) * x + carry;
        *i = prod % 10;                             // 곱의 마지막 한 자릿수만 저장
        carry = prod / 10;                          // 나머지 부분은 캐리로 넘김
    }

    while (carry) {                                 // 캐리가 남아 있는 동안
        multiplicand.push_back(carry % 10);
        carry = carry / 10;
    }
}

void factorial(int n) {
    vector<int> result;
    result.push_back(1);                            // 처음에는 결과값으로 1을 저장

    for (int i = 2; i <= n; i++)
        multiply(i, result);                        // 1*2*3*......*n을 차례로 곱함

    cout << "주어진 수의 팩토리얼: " << endl;

    reverse(result.begin(), result.end());          // 결과의 순서를 뒤집음

    vector<int>::iterator it;

    for (it = result.begin(); it != result.end(); it++)
        cout << *it;
}

int main() {
    factorial(50);
}

실행 결과

주어진 수의 팩토리얼:
30414093201713378043612608166064768844377641568960512000000000000

이처럼 배열 기반 곱셈을 활용하면 64비트 정수형의 최대값(약 1.8×10¹⁹)을 훌쩍 넘는 50! 같은 거대한 수도 정확하게 계산할 수 있습니다. 이 기법은 파이썬처럼 임의 정밀도 정수를 기본으로 지원하지 않는 언어에서 특히 유용합니다.