C 언어로 nPr(순열) 값을 계산하는 프로그램

이 글에서는 nPr 값을 계산하는 C 프로그램을 다룹니다. 여기서 P는 순열(Permutation)을 의미하고, n은 전체 데이터의 개수, r은 배열할 개수를 나타냅니다.

순열(nPr)이란?

순열은 데이터를 일정한 순서나 배열에 따라 나열하는 것을 말합니다. 순열과 조합의 차이는 다음과 같습니다. 순열은 요소를 배열(arrangement)하는 과정이고, 조합은 주어진 집합에서 요소를 선택(selection)하는 과정입니다. 즉, 순열은 순서가 중요하지만 조합은 순서가 중요하지 않습니다.

순열 공식

순열의 값은 다음 공식으로 계산할 수 있습니다.

nPr = n! / (n-r)!

예제 입력 및 출력

입력: n=5, r=2
출력: 20

예를 들어 5개의 데이터 중 2개를 순서 있게 나열하는 방법의 수는 5! / (5-2)! = 120 / 6 = 20가지입니다.

알고리즘

시작
단계 1 -> nPr 값을 계산하기 위한 함수 선언
    int cal_n(int n)
       IF n <= 1
          Return 1
    return n * cal_n(n-1)
단계 2 -> 최종 nPr 값을 계산하는 함수 선언
    int nPr(int n, int r)
       return cal_n(n) / cal_n(n-r)
단계 3 -> main() 함수에서
    변수를 int n=5, r=2로 선언
    nPr(n, r) 출력
종료

C 코드 구현

아래는 재귀 함수를 사용해 팩토리얼을 계산한 뒤, 그 결과로 nPr 값을 구하는 전체 C 코드입니다.

#include<stdio.h>

// nPr 계산을 위한 팩토리얼 함수
int cal_n(int n){
    if (n <= 1)
        return 1;
    return n * cal_n(n - 1);
}

// 최종 nPr 값을 계산하는 함수
int nPr(int n, int r){
    return cal_n(n) / cal_n(n - r);
}

int main(){
    int n = 5, r = 2;
    printf("%dP%d의 값은 %d입니다", n, r, nPr(n, r));
    return 0;
}

실행 결과

5P2의 값은 20입니다

코드 설명

cal_n() 함수는 재귀 호출을 통해 팩토리얼을 계산합니다. n이 1 이하가 되면 1을 반환하며 재귀가 종료되고, 그렇지 않으면 n에 n-1의 팩토리얼을 곱한 값을 반환합니다.

nPr() 함수는 위 공식 그대로 n의 팩토리얼을 (n-r)의 팩토리얼로 나누어 순열 값을 반환합니다.

이 프로그램의 시간 복잡도는 O(n)이며, 재귀 호출로 인해 간결하고 이해하기 쉬운 구조를 가지고 있습니다. 다만 매우 큰 n 값에서는 정수 오버플로우가 발생할 수 있으므로, 필요에 따라 long long 타입이나 반복문 기반 구현을 고려하는 것이 좋습니다.