팩토리얼(계승)을 활용하여 조합을 계산하는 C++ 프로그램

조합(Combination)은 n개의 서로 다른 원소 중에서 r개를 순서에 상관없이 선택하는 방법의 수를 의미합니다. 수학적으로는 다음 공식으로 표현할 수 있습니다.

C(n, r) = n! / (r! × (n−r)!)

이 공식을 그대로 코드로 옮기면 조합을 손쉽게 계산할 수 있습니다. 아래는 팩토리얼(계승)을 이용하여 조합을 계산하는 C++ 프로그램 예제입니다.

예제 코드

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}

int main() {
    int n, r, result;
    cout << "Enter n : ";
    cin >> n;
    cout << "\nEnter r : ";
    cin >> r;
    result = fact(n) / (fact(r) * fact(n - r));
    cout << "\nThe result : " << result;
    return 0;
}

실행 결과

Enter n : 10
Enter r : 4
The result : 210

코드 설명

1. 팩토리얼 계산 함수 — fact()

위 프로그램에서 fact() 함수는 재귀 호출(recursion) 방식으로 숫자의 팩토리얼 값을 계산합니다. 함수 내부의 핵심 로직은 다음과 같습니다.

if (n == 0 || n == 1)
    return 1;
else
    return n * fact(n - 1);

0!과 1!은 수학적으로 1로 정의되므로, n이 0 또는 1일 때는 1을 반환하는 기저 조건(base case)을 설정합니다. 그 외의 경우에는 n * fact(n-1) 형태로 자기 자신을 다시 호출하며, n부터 1까지의 곱을 차례대로 계산합니다.

2. 메인 함수 — main()

main() 함수에서는 사용자로부터 조합을 계산할 두 개의 정수 n과 r을 입력받습니다. 그런 다음 변수 result에 앞서 소개한 조합 공식인 n! / (r! × (n−r)!)의 계산 결과를 저장하고 화면에 출력합니다.

cout << "Enter n : ";
cin >> n;
cout << "\nEnter r : ";
cin >> r;
result = fact(n) / (fact(r) * fact(n - r));

참고 사항

위 예제에서는 int형을 사용하기 때문에 n이 커지면 팩토리얼 값이 매우 빠르게 증가하여 정수 오버플로우가 발생할 수 있습니다. 실무에서는 long long 타입을 사용하거나, 곱셈과 나눗셈의 순서를 조정하여 중간값을 작게 유지하는 방식으로 오버플로우를 방지하는 것이 좋습니다.