8번은 한번에 계단을 오르는 갯수가 한정되어 있을 때 입력받은 계단의 수를 오르는 경우의 수를 구하는 문제이다. 해당 문제 또한 for, while 그리고 재귀방식을 사용하여 풀어보았다.


문제 8) 계단 오르기

문제 8. 계단 오르기

계단을 한 번에 1계단 또는 2계단 오를 수 있다. N단의 계단을 오를 수 있는 총 가지 수를 계산하는 문제를 재귀함수로 구현 (0 < N <= 30)

- N = 2 일 경우 
    2가지 : (1,1), (2)
- N = 3 일 경우 
    3가지 : (1,1,1),(1,2),(2,1)
- N = 4 일 경우 
    5가지 : (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)
- N = 5 일 경우 
    8가지 : (1,1,1,2),(1,2,2),(2,1,2),(1,1,1,1,1),(1,2,1,1),(2,1,1,1),(1,1,2,1),(2,2,1)

해당 문제는 계단의 수(N)가 증가할 때 그 경우의 수에 일정한 규칙의 수열을 반환한다. 총 계단의 수가 하나씩 늘어날 때마다 바로 직전과 그 전의 연속된 두 가지 경우의 수의 합을 반환한다. 즉, f(n) = f(n - 1) + f(n - 2)이라는 점화식이 성립하게 된다.

이러한 규칙은 피보나치 수열이 가진 규칙과 동일하다. 피보나치에 더 자세히 알아보고자 한다면 이전에 포스팅했던 재귀 - 문제4. 피보나치 수열 출력을 참고하기 바란다.


코드 및 풀이

(1) while

# while 사용 

def stair_while():
    n = int(input("N = "))
    a = 0
    b = 1
    while n > 0 and n <= 30:
        a, b = b, a + b
        n -= 1
    return b
    

### 실행 ###
stair_while()

### 출력 ###
# N = 4
# 5

while문을 사용한 경우 파이썬의 값 교환방식을 사용하여 주어진 범위의 n을 만족할 경우에 반복문을 유지하도록 하였다. 그리고 n의 값에서 1씩 빼준다. 피보나치 수열의 규칙에 따라, 직전 두 경우의 수의 합을 반환하므로 b를 리턴해준다.


(2) for

# for 사용 

def stair_for():
    n = int(input("N = "))
    a = 0
    b = 1
    for i in range(n):
        a, b = b, a + b
    return b
    

### 실행 ###
stair_for()

### 출력 ###
# N = 10
# 89

for문을 사용한 경우에는 입력받은 값을 숫자형으로 받은 후 초기 값을 각각 0, 1로 설정했다. (피보나치 수열은 규칙상 시작하는 두 개의 수가 필요하다.) 그리고 n번만큼 반복문을 돌고 난 후 b의 값을 리턴해준다.


(3) recursive function

# recursive 사용

def recursive08():
    n = int(input("N = "))
    def stair_recursive(n):
        if n == 0 or n == 1:
            return 1
        r = stair_recursive(n - 1) + stair_recursive(n - 2)
        return r
    return stair_recursive(n)


### 실행 ###
recursive08()

### 출력 ###
# N = 10
# 89

재귀방식을 사용한 경우에는 n을 숫자형으로 받았다. 피보나치 수열에서 얻을 수 있는 점화식을 사용하여 값을 리턴한다. 피보나치 수열을 재귀로 푸는 경우에는 탈출조건이 n = 1, n = 0으로 2개이므로 각각의 경우에 1을 반환하여 돌아오면서 계산을 마치도록 하였다.


실행속도 측정해보기

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


# (1) while
avg(bin_while)
# 2.5879223152733175

# (2) for
avg(bin_for)
# 2.605831767170457

# (3) recursive
avg(recursive07)
# 2.621976392198121



마치며 : 피보나치 수열의 값을 재귀로 구할 때

재귀로 풀 때는 값이 커질 수록 반복으로 푼 방식과 비교했을 때 실행속도에 큰 차이가 났다. 즉, 재귀의 경우에는 입력값이 커지면 커질수록 실행속도가 어마어마하게 증가한다. 왜 그럴까?

앞서 구현해놓은 recursive08()에 입력값을 5라고 주자. 그러면 해당 메서드는 다음과 같은 계산을 실행한다.

# 편의상 재귀함수를 fib()로 표현한다. 
# fib(5)를 탈출조건을 만족할 때까지 풀어나가면 다음과 같다.

fib(5) 
= fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1) 
= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(0) + fib(-1)
= fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(0) + fib(-1)

fib(5)를 구하는 데에 fib(2)를 3번이나 독립적으로 계산해서 구한다. 반복문을 사용할 경우 경우의 수가 많아봤자 O(n)번인 반면, 재귀를 사용하면 시간복잡도가 O(2^(n/2)) 까지 증가한다. 또 입력값에서 탈출조건을 만날 때까지 연산해야 하는 재귀 함수가 2개이다. 해당 값은 각각의 조건을 거슬러 내려갈 때마다 탈출 조건을 만날 때까지 연산한 후 다시 자신을 호출하게 되므로 작은 입력값을 줄 때도 시간이 오래 걸리게 되는 것이다.

그렇기 때문에 피보나치 수열의 경우에는 반복문을 사용하여 값을 구하는 것이 재귀를 사용한 것보다 훨씬 효율적이라고 할 수 있다.



Julia Hwang

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