양의 정수 n의 팩토리얼(계승)은 1부터 n까지의 모든 양의 정수를 곱한 값으로, 1×2×3×…×n과 같이 표현됩니다. 예를 들어 5! = 1×2×3×4×5 = 120입니다. 반면 음수의 팩토리얼은 수학적으로 정의되지 않으므로 존재하지 않습니다.
여기서는 동적 프로그래밍(Dynamic Programming) 기법을 활용하여 입력된 숫자의 팩토리얼을 구하는 C++ 프로그램을 소개합니다. 동적 프로그래밍 방식에서는 이미 계산된 하위 문제의 결과를 배열에 저장하고 재활용하기 때문에, 재귀 호출에 비해 함수 호출 오버헤드가 없고 중복 계산도 발생하지 않는다는 장점이 있습니다.
알고리즘
시작
fact(int n):
숫자 n을 입력받음
변수 초기화
i = 1, result[1000] = {0}
result[0] = 1
i를 1부터 n까지 반복
result[i] = i * result[i-1]
결과(result[n]) 출력
끝핵심 아이디어
이 알고리즘의 핵심은 result[i] = i × result[i-1]이라는 점화식입니다. 즉, i번째 팩토리얼 값은 바로 이전 단계의 결과에 i를 곱하기만 하면 되므로, 각 단계의 결과를 배열에 저장해 두면 이후 계산에 그대로 활용할 수 있습니다. 이것이 바로 동적 프로그래밍의 기본 원리인 '메모이제이션(Memoization)'을 반복문 형태로 구현한 것입니다.
예제 코드
#include <iostream>
using namespace std;
int result[1000] = {0};
int fact(int n) {
if (n >= 0) {
result[0] = 1;
for (int i = 1; i <= n; ++i) {
result[i] = i * result[i - 1];
}
return result[n];
}
}
int main() {
int n;
while (1) {
cout << "팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): ";
cin >> n;
if (n == 0)
break;
cout << fact(n) << endl;
}
return 0;
}실행 결과
팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): 2 2 팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): 6 720 팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): 7 5040 팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): 10 3628800 팩토리얼을 계산할 정수를 입력하세요 (0 입력 시 종료): 0
복잡도 분석
- 시간 복잡도: O(n) — 1부터 n까지 한 번씩만 곱셈을 수행합니다.
- 공간 복잡도: O(n) — 각 단계의 결과를 저장하기 위해 크기 n+1의 배열을 사용합니다.
주의 사항
팩토리얼은 값이 매우 빠르게 커지는 함수입니다. 위 코드에서 사용한 int 자료형은 일반적으로 최대 약 21억(2³¹−1)까지만 표현할 수 있으므로, 13!부터는 범위를 초과하여 오버플로우가 발생합니다. 더 큰 수의 팩토리얼을 다루려면 result 배열과 반환값의 자료형을 long long(최대 약 922경)으로 변경하거나, 임의 정밀도 연산을 지원하는 라이브러리를 사용하는 것이 좋습니다.