3장 - (아주 쉽게 설명한) 조합을 계산하는 함수를 만들어 봅시다.

3장 함수에 관한 보충 설명입니다. 자세한 내용은 쉽게 다가가는 최신 프로그래밍: 코틀린 - 3.1.4 함수 응용을 참고하기 바랍니다. 함수 사용 방법에 익숙해지는 첫 단계는 자신이 잘 아는 (너무 복잡하지 않은) 수학 공식을 함수로 만들어보는 것입니다. 여기서는 조합(combination) 를 구하는 프로그램을 작성해 보려고 합니다.

조합 C(n, k) = n!/k!(n-k)! 이므로, 조합을 구하려면 계승(factorial)을 구해야 합니다. 3의 계승은 3!=1x2x3=6 입니다. n!에서 n은 자연수(n≥1)이며, n보다 같거나 작은 모든 양의 정수 곱입니다. 0!은 어떻게 정의될까요? 0!=1입니다(^^~). 1!부터 계승을 구하는 게 일반적이죠. 1!은 당연히 1입니다.

함수를 정의할 때 가장 먼저 할 일은 함수의 서명(signature)을 선언하는 것입니다(114쪽의 3.1 함수 정의를 참고하세요). 함수 factorial()의 형식인자는 Int 타입 1개입니다. 이 함수의 반환 값 타입도 Int로 선언해도 될까요? 

fun factorial( n: Int ): Int

이렇게 선언하는 게 틀리진 않았지만(컴파일시간 오류(compile time error)는 없지만), 실행시간 오류(runtime error)가 발생할 가능성이 높습니다. 왜 그럴까요? 10! = 3,628,800, 11! = 39,916,800, 12! = 479,001,600, 13! = 6,227,020,800, ... 숫자 13부터는 Int 타입의 최대값을 초과하기 때문이죠(32쪽, 1.5 숫자 타입). 

어떻게 수정할까요? 함수 factorial() 반환 값의 타입을 Long으로 바꾸거나 실수형(Float, Double)으로 바꿔야 합니다. 

fun factorial( n: Int ): Long

factorial()의 형식인자 타입도 Int에서 UInt로 바꾸면 어떨까요? 아쉽게도 for 루프로 구현할 때 범위 연산자(2..n)는  Int 타입만 사용할 수 있습니다. 이제 factorial() 함수를 아래처럼 만들면 됩니다. 

fun factorial(n: Int): Long { 
    var result: Long = 1L   // 1L은 Long 타입 상수입니다.
    for (i in 2..n) {       // 1은 굳이 곱할 필요가 없겠죠.
        result *= i
    }
    return result
}

잠깐! 0이나 1을 factorial() 함수의 형식인자에 전달하면 for 루프가 제대로 동작할까요? 좋은 지적입니다. 머리로 고민하지 말고, 함수가 제대로 동작하는지 직접 테스트해보는 게 가장 좋은 방법입니다. n1=0, n2=1, n3 =-1일 때, factorial(n1), factorial(n2), factorial(n3)는 각각 어떤 결과가 나올까요?

fun factorial(n: Int): Long { 
    var result = 1L   // Long 타입 선언은 생략할 수 있습니다.
    for (i in 2..n) {       
        result *= i
    }
    return result
}

fun main() {
    val n1 = 0
    val n2 = 1
    val n3 = -1
    println("factorial($n1) = ${factorial(n1)}")
    println("factorial($n2) = ${factorial(n2)}")
    println("factorial($n3) = ${factorial(n3)}")
}

for 루프의 범위 연산자(2..n)는 2부터 n까지(n도 포함) Int 타입 정수입니다. n이 0, 1, 또는 -1이면, 2 보다 크거나 같아야 하는 범위가 성립하지 않기 때문에 for 루프를 실행하지 못합니다. for 루프를 건너뛰면, 지역 변수 result는 초기값 1L을 갖고 있어 이 함수의 반환 값은 1입니다. factorial() 함수는 범위 조건을 만족하지 않는 값이 전달되면 항상 1을 반환합니다.

이제 함수 factorial()을 사용해 조합을 구하는 함수 combination()를 만들어야겠죠. 조합 C(n, k)은 2개의 형식 인자 n과 k가 필요하며, 계승 연산을 하기 때문에 반환 값의 타입도 Long으로 선언하는 게 좋겠죠. 

fun combination( n: Int, k: Int ): Long

combination() 함수를 구현하려면 조합이 어떤 기능을 하는지 알아야겠죠. 중복되지 않은 n개에서 k개를 선택하는 방법의 수가 조합입니다. 축구국가대표 후보 10명(n=10) 중 최종 후보 5명(k=5)을 선발하는 방법의 수를 구하는 것이 조합입니다. k는 n보다 클 수 없습니다. 또, k가 0이거나 n이면, 방법은 하나 뿐입니다. k=0은 10명 중 아무도 국가대표로 선발하지 않는 것이며, n=k는 전원 국가대표로 선발하는 것입니다.

fun factorial(n: Int): Long {
    var result = 1L
    for (i in 2..n) {
        result *= i
    }
    return result
}

fun combination(n: Int, k: Int): Long {
    if (k > n) return 0
    if (k == 0 || k == n) return 1
    return factorial(n) / (factorial(k) * factorial(n - k))
}

fun main() {
    val n = 5
    val k = 2
    println("C($n, $k) = ${combination(n, k)}") 
}

 

이런 특수한 조건 (k=0, n=k)이 아니라면, 함수 factorial()을 사용해 조합 C(n, k) (n>k)을 구해야합니다. C(n, k) = n!/k!(n-k)!  를 코드로 옮기면 됩니다. 아래처럼 코딩하면 결과가 어떻게 나올까요?

return factorial(n) / factorial(k) * factorial(n-k)

괄호를 뺀 것과 괄호를 한 것은 연산 결과가 전혀 다릅니다. 나눗셈과 곱셈은 연산 우선순위가 같기 때문에 좌결합법칙(왼쪽부터 차례대로 계산)이 적용됩니다. factorial(n) / factorial(k) 가 먼저 실행됩니다. 따라서, 아래처럼 분모를 괄호로 묶어야 합니다.

return factorial(n) / (factorial(k) * factorial(n-k))

지금 설명한 내용은 꼭 코틀린에만 적용되는 건 아니며, 다른 프로그래밍 언어로 구현할 때도 마찬가지입니다.