문제 설명
이항계수는 조합론에서 두 가지를 조합하여 선택할 때 사용되는 개념으로,
C(n, k) 형식으로 표현됩니다. 이 때,
C(n, k) 는 n개의 항 중에서 k개를 선택하는 경우의 수를 의미합니다.
이 문제에서는 이항계수를 구하는 프로그램을 작성해야 합니다.
문제
두 정수 n과 k가 주어질 때, n개 중에서 k개를 뽑는 경우의 수를 출력하는 프로그램을 작성하시오.
입력
- 첫 번째 줄에 두 정수 n(0 ≤ n ≤ 30), k(0 ≤ k ≤ n) 이 주어진다.
출력
- 주어진 n과 k에 대한 이항계수를 출력한다.
이항계수의 정의
이항계수는 다음과 같은 수식으로 정의됩니다:
C(n, k) = n! / (k! * (n - k)!)
여기서 n! (n 팩토리얼)은 1부터 n까지의 정수를 모두 곱한 값입니다.
예를 들어,
5! = 5 × 4 × 3 × 2 × 1 = 120 입니다.
문제 풀이 과정
1단계: 입출력 처리
문제의 출발점인 사용자 입력 데이터를 처리합니다.
입력으로 주어진 n과 k는 둘 다 정수이므로,
Scanner 클래스를 사용하여 입력을 받을 수 있습니다.
import java.util.Scanner;
public class BinomialCoefficient {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
// 앞으로의 코드에서 n과 k를 이용해 이항계수를 계산
}
}
2단계: 팩토리얼 계산 함수 작성
팩토리얼을 계산하는 함수를 구현합니다.
이곳에서는 재귀 함수를 통해 n 팩토리얼을 계산하겠습니다.
public static int factorial(int num) {
if (num == 0) return 1; // 0! = 1
return num * factorial(num - 1);
}
3단계: 이항계수 계산 함수 작성
이항계수를 계산하는 전용 함수를 작성합니다.
앞선 단계에서 구현한 factorial 함수를 활용합니다.
public static int binomialCoefficient(int n, int k) {
return factorial(n) / (factorial(k) * factorial(n - k));
}
4단계: 최종 코드 작성
이제 모든 기능을 모아서 최종 코드를 완성합니다.
import java.util.Scanner;
public class BinomialCoefficient {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
System.out.println(binomialCoefficient(n, k));
}
public static int factorial(int num) {
if (num == 0) return 1;
return num * factorial(num - 1);
}
public static int binomialCoefficient(int n, int k) {
return factorial(n) / (factorial(k) * factorial(n - k));
}
}
5단계: 시간 복잡도 분석
위의 알고리즘은 팩토리얼을 계산하는 데에 재귀를 사용하였습니다.
팩토리얼 함수의 시간 복잡도는 O(n) 입니다.
따라서 총 알고리즘의 시간 복잡도는 O(n) * 3 (팩토리얼을 세 번 호출) 이므로 O(n)으로 분석할 수 있습니다.
결론
이항계수를 구하는 방법에 대해 살펴보았습니다.
이 문제는 조합론의 기초적인 개념을 이해하는 데 도움이 되며,
실제 코딩테스트에 종종 출제되는 문제 유형입니다.
또한 재귀와 팩토리얼 개념을 활용하여 해결할 수 있어
자바 프로그래밍에 대한 이해도를 높일 수 있는 좋은 문제입니다.
다음에는 이항계수의 동적 프로그래밍을 학습하여 성능을 개선할 수 있는 방법을 다뤄보겠습니다.
이칸계수의 다양한 응용도 함께 살펴보는 시간을 갖도록 하겠습니다.