안녕하세요! 오늘은 코틀린을 사용하여 이항계수를 구하는 방법에 대해 알아보겠습니다. 이항계수는 조합(combination)에서 중요한 개념으로, 주어진 n개의 객체 중 k개의 객체를 선택하는 방법의 수를 나타냅니다. 이 항목은 코딩테스트에서 자주 출제되므로 반드시 숙지해야 합니다.
문제 설명
어떤 정수 n과 k가 주어졌을 때, nCk (n choose k)를 계산하는 프로그램을 작성하시오. 이항계수는 다음과 같은 수식으로 정의됩니다:
C(n, k) = n! / (k! * (n - k)!)
여기서 n!은 n의 팩토리얼을 의미합니다. 팩토리얼은 1부터 n까지의 모든 자연수의 곱입니다.
입력 형식
첫 번째 줄에 정수 n(0 ≤ n ≤ 30)과 k(0 ≤ k ≤ n)가 주어진다.
출력 형식
nCk의 값을 출력한다.
예제 입력
5 2
예제 출력
10
문제 해결 방법
이 문제를 해결하기 위해서는 다음의 두 가지 방법을 사용할 수 있습니다:
- 재귀를 이용한 팩토리얼 계산
- 동적 프로그래밍을 이용한 이항계수 계산
1. 재귀를 이용한 팩토리얼 계산
가장 기본적인 방법은 재귀를 이용하여 팩토리얼을 계산하는 것입니다. 이 방법은 이해하기 쉽지만 n이 커질수록 비효율적일 수 있습니다. 다음은 팩토리얼을 재귀적으로 계산하는 코틀린 예제입니다:
fun factorial(n: Int): Long {
return if (n == 0 || n == 1) 1 else n * factorial(n - 1)
}
2. 동적 프로그래밍을 이용한 이항계수 계산
이항계수를 효율적으로 계산하기 위해서는 동적 프로그래밍을 활용할 수 있습니다. 이항계수는 Pascal의 삼각형의 성질을 통해 계산할 수 있으며, 다음의 점화식으로 정의됩니다:
C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
기저 사례는 다음과 같습니다:
- C(n, 0) = 1 (n >= 0)
- C(n, n) = 1 (n >= 0)
Pascal의 삼각형에 따라 동적 프로그래밍 배열을 통해 이항계수를 계산해보겠습니다:
fun binomialCoefficient(n: Int, k: Int): Long {
val dp = Array(n + 1) { LongArray(k + 1) }
for (i in 0..n) {
for (j in 0..minOf(i, k)) {
if (j == 0 || j == i) {
dp[i][j] = 1
} else {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
}
}
}
return dp[n][k]
}
코드 통합 예제
위의 방법들을 바탕으로 최종 코드를 작성해보겠습니다:
fun main() {
val input = readLine()!!.split(" ").map { it.toInt() }
val n = input[0]
val k = input[1]
println(binomialCoefficient(n, k))
}
fun binomialCoefficient(n: Int, k: Int): Long {
val dp = Array(n + 1) { LongArray(k + 1) }
for (i in 0..n) {
for (j in 0..minOf(i, k)) {
if (j == 0 || j == i) {
dp[i][j] = 1
} else {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
}
}
}
return dp[n][k]
}
결론
이항계수를 계산하는 방법에 대해 알아보았습니다. 재귀와 동적 프로그래밍을 통해 이 문제를 해결할 수 있으며, 각 방법의 장단점을 이해하는 것이 중요합니다. 이항계수는 조합론뿐만 아니라 많은 분야에서 응용될 수 있으니, 이 개념을 확실히 이해해 두는 것이 좋습니다.
앞으로도 코틀린을 이용한 다양한 알고리즘 문제풀이 과정을 지속적으로 탐구하길 바랍니다. 감사합니다!