코딩 테스트에서는 조합(combination)과 같은 조합론적 문제를 자주 만납니다. 조합이란 주어진 집합에서 요소의 순서를 고려하지 않고 선택하는 경우의 수를 말합니다. 본 강좌에서는 조합의 개념을 깊이 이해하고, C#을 사용하여 이러한 문제를 해결하는 방법을 배우도록 하겠습니다.
1. 조합의 정의
조합은 n개의 원소 중에서 r개의 원소를 선택하는 경우의 수를 의미합니다. 조합의 수는 다음과 같은 식으로 계산할 수 있습니다:
C(n, r) = n! / (r! * (n – r)!)
여기서 n!은 n의 팩토리얼로, n × (n-1) × (n-2) × … × 1을 의미합니다. r!과 (n – r)!도 각각 r의 팩토리얼과 (n – r)의 팩토리얼입니다.
2. 조합 문제 예시
아래는 조합과 관련된 문제입니다.
문제: 팀 구성
5명의 학생이 있습니다. 이 중에서 3명의 학생을 뽑아 팀을 구성하려 합니다. 가능한 팀의 경우의 수를 구하세요. 단, 각 학생은 고유하게 번호를 가지고 있으며, 번호로 학생을 구별합니다. 예를 들어, 학생 1, 2, 3을 선택한 팀과 학생 2, 1, 3을 선택한 팀은 같은 팀으로 간주합니다.
3. 문제 풀이 과정
3.1 규명하기
우선 문제를 분해해 보겠습니다. 우리는 5명의 학생 중 3명을 선택할 것입니다. 조합의 공식을 사용하여 이 문제를 해결할 수 있습니다.
3.2 파라미터 지정
이 문제에서:
- n = 5 (전체 학생 수)
- r = 3 (선택할 학생 수)
3.3 조합 수 계산
조합 공식을 사용하여 경우의 수를 계산해 보겠습니다.
C(5, 3) = 5! / (3! * (5 – 3)!) = 10
그러므로 가능한 팀의 경우의 수는 총 10가지입니다.
4. C#으로 구현하기
이제 위의 조합 공식을 C#으로 구현해 보겠습니다.
using System;
class Program
{
static void Main(string[] args)
{
int n = 5; // 전체 학생 수
int r = 3; // 선택할 학생 수
Console.WriteLine("팀 구성 경우의 수: " + Combination(n, r));
}
// 조합을 계산하는 메서드
static int Combination(int n, int r)
{
return Factorial(n) / (Factorial(r) * Factorial(n - r));
}
// 팩토리얼을 계산하는 메서드
static int Factorial(int num)
{
if (num <= 1)
return 1;
return num * Factorial(num - 1);
}
}
위의 코드에서 우리는 ‘Combination’ 메서드를 정의하여 조합을 계산하고, ‘Factorial’ 메서드로 팩토리얼을 계산합니다. 이 코드를 실행하면 가능한 팀의 경우의 수인 10이 출력됩니다.
5. 다양한 사용 사례
조합은 다양한 상황에서 사용될 수 있습니다:
- 팀 구성: 몇 명의 인원을 한 팀으로 구성할 때 사용할 수 있습니다.
- 조합 게임: 카드 게임이나 보드 게임에서 카드 조합을 통해 전략을 세우는 데 유용합니다.
- 데이터 샘플링: 대규모 데이터에서 샘플을 선정할 때 조합을 사용합니다.
6. 결론
조합의 개념은 코딩 테스트에서 중요한 역할을 하며, 이를 통해 다양한 문제를 해결할 수 있습니다. 이번 강좌를 통해 조합의 기본을 이해하고 C#을 활용하여 간단한 문제를 해결하는 방법을 배웠습니다. 앞으로 더 복잡한 조합 문제에도 도전해 보시기 바랍니다.
7. 연습 문제
아래의 연습 문제를 통해 조합을 연습해 보세요.
- 문제 1: 8명의 친구 중 4명을 뽑는 경우의 수를 구하시오.
- 문제 2: 7장의 카드 중 2장을 뽑는 경우의 수를 구하시오.
각 문제를 해결한 후, C# 코드를 작성해보는 것도 좋은 연습이 될 것입니다.
8. 추가 자료
자세한 조합 관련 자료는 다음 링크를 통해 참고하시기 바랍니다: