코딩테스트를 준비하는 과정에서 알고리즘 문제는 반드시 풀어야 할 필수 항목 중 하나입니다.
오늘은 C#을 사용하여 이항계수를 구하는 문제를 풀어보겠습니다.
이항계수는 조합(combination)을 계산하는 수학적 방법론으로, 주어진 n과 k에 대해 nCk를 구하는 것입니다.
이항계수란?
이항계수는 주어진 n개의 요소 중에서 k개의 요소를 선택하는 경우의 수를 나타냅니다.
수학적으로 이항계수는 다음과 같이 정의됩니다:
C(n, k) = n! / (k! * (n-k)!)
여기서 n!은 n 팩토리얼(factorial)을 의미합니다.
팩토리얼은 주어진 수 n의 모든 양의 정수를 곱한 값입니다:
n! = n * (n-1) * (n-2) * ... * 2 * 1
예를 들어, C(5, 2)는 다음과 같이 계산됩니다:
C(5, 2) = 5! / (2! * (5-2)!) = 5 * 4 / (2 * 1) = 10
문제 정의
주어진 n과 k에 대해 이항계수 C(n, k)를 계산하는 프로그램을 작성하시오.
입력은 두 개의 정수 n과 k가 주어지며 (0 ≤ k ≤ n ≤ 10,000)입니다.
출력은 C(n, k)의 값을 출력하는 것입니다.
알고리즘 접근 방법
이 문제를 해결하기 위해 우리는 두 가지 주요 접근 방법을 사용할 수 있습니다.
첫 번째는 재귀적인 방법이고, 두 번째는 반복적인 방법입니다.
그러나 n이 최대 10,000까지 가능하므로 재귀적인 방법은 스택 오버플로우가 발생할 수 있습니다.
따라서 반복적인 방법으로 접근하겠습니다.
1. 반복적인 방법
반복적인 방법을 사용하여 이항계수를 계산하기 위해,
우리는 팩토리얼을 계산하는 함수를 만들고 이 함수를 사용하여 C(n, k)를 계산하겠습니다.
그러나 n과 k의 값이 클 경우 팩토리얼의 값이 매우 커지므로,
메모리 사용을 줄이기 위해 nCk의 값을 재귀적으로 계산하면 됩니다.
2. 최적화된 이항계수 계산
이항계수의 성질을 이용하여 다음과 같은 방식으로 계산할 수 있습니다:
C(n, k) = C(n, n-k)
따라서 k가 n/2보다 클 경우 k를 n-k로 변경하여 계산할 수 있습니다. 이는 계산을 더 효율적으로 만듭니다.
C# 코드 구현
이제 알기 쉽게 C# 코드를 구현해 보겠습니다.
아래는 이항계수를 계산하는 C# 코드입니다:
using System;
class Program
{
static void Main(string[] args)
{
// 입력 받기
string[] inputs = Console.ReadLine().Split(' ');
int n = int.Parse(inputs[0]);
int k = int.Parse(inputs[1]);
// C(n, k) 계산
long result = BinomialCoefficient(n, k);
// 결과 출력
Console.WriteLine(result);
}
static long BinomialCoefficient(int n, int k)
{
// 최적화: k가 n/2보다 큰 경우
if (k > n / 2)
{
k = n - k;
}
long result = 1;
for (int i = 0; i < k; i++)
{
result *= (n - i);
result /= (i + 1);
}
return result;
}
}
코드 설명
위 코드의 작동 방식은 다음과 같습니다:
- 사용자로부터 n과 k를 입력 받습니다.
- BinomialCoefficient 메서드를 호출하여 이항계수를 계산합니다.
- 결과를 출력합니다.
BinomialCoefficient 메서드는 k의 값을 n/2와 비교하여 최적화된 계산을 수행합니다.
이후 반복문을 통해 이항계수를 실제로 계산합니다.
이 방법은 시간 복잡도가 O(k)로 효율적입니다.
테스트 케이스
다음은 코드의 작동을 확인하기 위한 테스트 케이스입니다:
입력: 5 2
출력: 10
입력: 10 3
출력: 120
입력: 10 7
출력: 120 // C(10, 3)와 같습니다.
입력: 10000 5000
출력: 대략적인 값 (이 경우 계산 시간이 걸릴 수 있습니다.)
마무리
오늘은 C#을 사용하여 이항계수를 계산하는 문제를 해결했습니다.
반복적인 방법과 최적화된 계산 방식을 통해 효율적으로 이항계수를 구할 수 있었습니다.
코딩테스트 준비에 이 글이 도움이 되기를 바랍니다.
앞으로 더 다양한 알고리즘 문제를 다루는 강좌를 연재할 예정이니 많은 관심 부탁드립니다.