재귀 관계를 활용해 nCr 조합을 계산하는 C++ 프로그램

개요

조합(nCr)은 서로 다른 n개의 대상 중에서 순서에 상관없이 r개를 선택하는 경우의 수를 뜻하며, 수학적으로 다음 공식으로 정의됩니다.

nCr = n! / (r! × (n − r)!)

이 글에서는 팩토리얼을 직접 계산하지 않고 재귀 관계(점화식)를 이용해 조합을 구하는 C++ 프로그램을 소개합니다. 여기서 활용되는 점화식은 다음과 같습니다.

nCr = (n / r) × (n−1)C(r−1), 단 r = 0이면 nC0 = 1

알고리즘

시작
    함수 CalCombination():
        매개변수: n, r
        함수 본문:
            r > 0이면 (n / r) × CalCombination(n − 1, r − 1) 반환
            그렇지 않으면 1 반환
종료

예제 코드

#include<iostream>
using namespace std;

// 재귀 관계 nCr = (n/r) × (n-1)C(r-1)을 이용한 조합 계산 함수
float CalCombination(float n, float r) {
    if (r > 0)
        return (n / r) * CalCombination(n - 1, r - 1);
    else
        return 1; // 기저 사례: nC0 = 1
}

int main() {
    float n, r;
    int res;
    cout << "n의 값을 입력하세요: ";
    cin >> n;
    cout << "r의 값을 입력하세요: ";
    cin >> r;
    res = CalCombination(n, r);
    cout << "\n가능한 조합의 개수는 다음과 같습니다: nCr = " << res;
}

실행 결과

n의 값을 입력하세요: 7
r의 값을 입력하세요: 6
가능한 조합의 개수는 다음과 같습니다: nCr = 7

코드 설명

함수 CalCombination()은 인자로 받은 n과 r에 대해 위 점화식을 그대로 재귀적으로 적용합니다. r이 0보다 크면 (n / r) × (n−1)C(r−1)을 반환하고, r이 0이 되면 기저 사례인 1을 반환하여 재귀 호출을 종료합니다.

예를 들어 n = 7, r = 6을 입력하면 7C6 = 7! / (6! × 1!) = 7이므로 결과값 7이 출력됩니다. 각 단계에서 곱해지는 분수들이 서로 약분되어 최종적으로 n이 그대로 남는 원리입니다.

참고 사항

부동소수점 연산의 특성상 n이 매우 커지면 오차가 누적될 수 있습니다. 따라서 실무에서는 정수형(long long)을 사용하거나 파스칼 삼각형을 활용한 동적 계획법(DP) 방식으로 조합을 계산하는 것이 더 안전하고 효율적입니다.