9번은 이항계수의 계산값을 재귀방식으로 구하는 문제이다. 여기서 이항계수(Binominal Coefficient)는 다음을 만족한다.



이항계수는 $nCk$ 나 $C(n, k)$로 쓰기도 한다. 이항계수는 다음과 같은 성질을 가지는데 해당 문제는 다음 성질을 가진다.

실제로 수를 넣어 계산해보면 동일하다.


두번째 성질은 다음과 같다. 이는 파스칼의 법칙이라고 부른다.


문제 9) 이항계수 계산하기

위의 성질을 이용하여 다음 문제를 풀 수 있다.

문제 9. 이항계수 계산하기

입력 : 양의 정수 n (1 <= n <= 50, k: n/2)로 설정
경우 1 : 재귀함수를 사용하여 결과값과 실행시간 출력
경우 2 : 반복문을 사용하여 결과값과 실행시간 출력

이항계수 계산은 다음과 같은 규칙을 이용한다.


코드 및 풀이

재귀 방식으로 작성한 코드는 다음과 같다.

def recursive09():
    n = int(input("Input the number : "))
 
    def bino_recursive(n, k=(n//2)):
        if n == k or k == 0 or n == 1:
            return 1
        if k == 1:
            return n
        if n > 50:
            return "Too big!"
  
        r = bino_recursive(n - 1, k) + bino_recursive(n - 1, k - 1)
        return r
    return bino_recursive(n)

매개변수로 각각 n, k 2개를 받는 재귀함수를 정의한다. 문제에서 kn // 2로 정의하였으므로 매개변수에서 기본으로 정의해준다. 문제에서 이항계수를 계산하는 수식을 사용하여 리턴 값을 계산하도록 하였다.

이 문제에서는 탈출조건이 여러 개인데, 먼저 nk의 값이 같을 때와 k = 0, n = 1일 때는 각각 $0C0$, $nC0$의 값인 1을 리턴하도록 하였다. 또, k = 1일 때는 n으로 리턴값을 정의해주었으며, 문제에서 입력받는 n은 50을 초과하지 않으므로 예외처리를 해주었다.


실행시간 측정해보기

메서드의 실행시간을 측정하는 runtime()를 여러 번 실행하여 실행시간의 평균값을 측정하였다.

# 작성한 메서드를 반복 실행하여 나온 실행속도의 평균값 구하는 함수를 avg()로 정의하였다.

# (3) recursive
# 10,000번 실행했을 때
avg(recursive09)
# 0.004200054943794385

# 100,000번 실행했을 때
avg(recursive09)
# 0.03512693246011622

# 1,000,000번 실행했을 때
avg(recursive09)
# 0.4098219453881029

# 10,000,000번 실행했을 때
avg(recursive09)
# 3.633702998238732



Julia Hwang

디발자를 꿈꾸는 웹개발자의 블로그입니다.