20240109_C#에서의 순열

오늘의 TIL은 알고리즘 문제를 풀면서 만난 순열에 대한 내용이다.

 

순열은 수학에서 배우는 경우의 수를 찾는 방법에서 사용되는 용어로 보통은  nPr로 알고 있다.

 

나무위키의 내용을 살펴보면

 

https://namu.wiki/w/%EC%88%9C%EC%97%B4

순열 - 나무위키

 

순열(Permutation)은 서로 다른 n개의 원소에서 r(단, 0 <= r <= n 일 때)개를

 

중복없이 순서를 고려하여 선택하거나 나열하거나 하는 것을 말한다.

 

n개의 원소에서 1개를 선택하여 나열하는 경우의 수는 n이고,

 

n개의 원소에서 2개를 선택하여 나열하는 경우의 수는 n * (n - 1)이다.

 

n개의 원소에서 3개를 선택하여 나열하는 경우의 수는 n * (n - 1) * (n - 2)이다.

 

...

 

n개의 원소에서 r개를 선택하여 나열하는 경우의 수는 n * (n - 1) * (n - 2) * ... * (n - r + 1)이다.

 

이를 팩토리얼을 이용하여 간략화 하면 nPr = n! / (n - r)! 이 된다.

 

이를 C#에서 구현하면 아래와 같다.

 

static int Permutation(int n, int r)
{
    return Factorial(1, n) / Factorial(1, (n - r));
}

static int Factorial(int start, int end)
{
    int result = 1;
    
    for (int i = start; i <= end; i++)
    {
    	result *= i;
    }
    
    return result;
}

 

 

순열을 구현하는 김에 순열과 함께 등장하는 조합(nCr = n! / (n - r)! * r!)을 같이 구현하면 아래와 같다.

 

static int Combination(int n, int r)
{
    return Factorial(1, n) / (Factorial(1, (n - r)) * Factorial(1, r));
}

 

 

오늘은 알고리즘 문제를 푸는 과정에서 수학적인 내용이 나와서 순열과 조합 부분을 공부하면서

 

이를 C#에서 구현하는 것을 도전해봤는데, 처음에는 구현하기 어렵다고 느꼈으나,

 

이후에 Factorial을 도입하여 Factorial을 구현하는 것을 연결함으로써 해결하였다.

 

코딩을 하는 부분에서 수학적인 지식이 필요한 경우가 있는 것이 느껴지는데,

 

오늘 오랫만에 수학적인 생각을 할 수 있는 문제를 풀면서 순열과 조합을 공부할 수 있는 기회가 되었다.

 

이 순열과 조합을 이후에 사용할 알고리즘 북에 추가함으로써 이후에 사용할 수 있는 도구가 늘었다.