C++에서 조합과 순열을 계산하는 방법 완벽 가이드

조합(Combination)과 순열(Permutation)은 조합론(Combinatorics)의 핵심 개념입니다. 순열은 n개의 원소 중에서 하나씩, 일부씩 또는 전체를 한 번에 선택하여 나열하는 서로 다른 순서의 배열을 의미하며, 조합은 순서와 상관없이 원소를 선택하는 서로 다른 방법의 수를 의미합니다.

순열과 조합의 공식

전체 n개의 원소 중 r개의 원소를 배열할 때의 순열 개수는 다음과 같습니다.

전체 n개의 원소 중 r개의 원소를 선택할 때의 조합 개수는 다음과 같습니다.

C++ 구현 예제

아래는 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, comb, per;
    cout << "Enter n : ";
    cin >> n;
    cout << "\nEnter r : ";
    cin >> r;
    
    comb = fact(n) / (fact(r) * fact(n - r));
    cout << "\nCombination : " << comb;
    
    per = fact(n) / fact(n - r);
    cout << "\nPermutation : " << per;
    
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter n : 5
Enter r : 3
Combination : 10
Permutation : 60

코드 설명

이 프로그램의 동작 원리는 다음과 같습니다.

1. 팩토리얼 함수(fact): 재귀 호출을 사용하여 n!을 계산합니다. n이 0 또는 1이면 1을 반환하고, 그 외에는 n × (n-1)!을 반환합니다.

2. 조합 계산: C(n, r) = n! / (r! × (n-r)!) 공식을 적용합니다. 위 예제에서는 5C3 = 10이 됩니다.

3. 순열 계산: P(n, r) = n! / (n-r)! 공식을 적용합니다. 위 예제에서는 5P3 = 60이 됩니다.

즉, 5개의 원소 중 3개를 선택하는 경우의 수는 10가지이며, 선택 후 순서까지 고려하면 60가지가 됩니다.