조합(nCr)과 순열(nPr)이란?
C 프로그래밍 언어에서 nCr은 조합(combination)을 의미합니다. 조합은 n개의 대상 가운데 r개를 선택하는 방법으로, 선택된 대상들의 순서는 고려하지 않습니다.
nPr은 순열(permutation)을 의미합니다. 순열은 n개의 대상 가운데 r개를 뽑아 일정한 순서 또는 배열로 나열하는 방법입니다.
순열과 조합 공식
C 언어에서 주어진 두 수의 순열과 조합을 구하는 공식은 다음과 같습니다.
- nCr = n! / (r! × (n−r)!)
- nPr = n! / (n−r)!
nCr을 구하는 로직은 다음과 같습니다.
result = factorial(n)/(factorial(r)*factorial(n-r));
nPr을 구하는 로직은 다음과 같습니다.
result = factorial(n)/factorial(n-r);
예제 코드
다음은 사용자로부터 두 수를 입력받아 해당 수의 순열과 조합을 계산하는 C 프로그램입니다.
#include <stdio.h>
long factorial(int);
long find_ncr(int, int);
long find_npr(int, int);
int main(){
int n, r;
long ncr, npr;
printf("Enter the value of n and r\n");
scanf("%d%d",&n,&r);
ncr = find_ncr(n, r);
npr = find_npr(n, r);
printf("%dC%d = %ld\n", n, r, ncr);
printf("%dP%d = %ld\n", n, r, npr);
return 0;
}
long find_ncr(int n, int r) {
long result;
result = factorial(n)/(factorial(r)*factorial(n-r));
return result;
}
long find_npr(int n, int r) {
long result;
result = factorial(n)/factorial(n-r);
return result;
}
long factorial(int n) {
int c;
long result = 1;
for (c = 1; c <= n; c++)
result = result*c;
return result;
}
프로그램 동작 원리
- factorial() 함수는 반복문을 이용해 1부터 n까지의 값을 모두 곱하여 n!을 계산합니다.
- find_ncr() 함수는 조합 공식인 n!/(r!×(n−r)!)을 적용하여 결과를 반환합니다.
- find_npr() 함수는 순열 공식인 n!/(n−r)!을 적용하여 결과를 반환합니다.
팩토리얼 값은 매우 빠르게 증가하기 때문에 long 자료형을 사용하며, n이 커질 경우 오버플로가 발생할 수 있다는 점에 유의해야 합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 출력을 확인할 수 있습니다.
Enter the value of n and r 5 2 5C2 = 10 5P2 = 20
n=5, r=2를 입력한 경우, 조합 5C2는 10, 순열 5P2는 20으로 계산됩니다. 같은 선택이라도 순서까지 고려하는 순열의 경우의 수가 더 많다는 점을 확인할 수 있습니다.