[재귀호출] LeetCode 70. Climbing Stairs

 

1과 2의 합으로 n을 만드는 경우의 수를 구한다.

 

1. 재귀호출 (브루트포스. 모든 경우의 수를 다 구한다)

예를 들어 1과 2의 합으로 4를 만드는 경우의 수를 봐보자.

1+1+1+1, 1+1+1+2, 1+1+2, 1+2+1, 1+2+2, ... 이런식으로 모든 경우의 수를 다 해보는 것이다.

 

class Solution:
    
    def __init__(self):
        self.cnt = 0
    
    def do(self, result,n):
        
        if result == n:
            self.cnt += 1
            return
        
        if result > n:
            return
        
        for i in [1,2]:
            self.do(result+i,n)
            
            
            
    def climbStairs(self, n: int) -> int:
   
        self.do(0,n)
        return self.cnt

 

또는

 

class Solution:            
            
    def climbStairs(self, n: int) -> int:
              
        return self.__climbStairs(0,n)

    
    def __climbStairs(self,i, n):
        if i > n :
            return 0
        
        if i == n:
            return 1
        
        return self.__climbStairs(i+1,n) + self.__climbStairs(i+2,n)

 

시간복잡도 : O(2^N)

공간복잡도 : O(2^N)

 

2. 재귀호출 memo 활용 (bottom-up 방식)

class Solution:            
            
    def climbStairs(self, n: int) -> int:
        
        # memo[i] :
        memo = [0]*(n+1)
        return self.__climbStairs(0,n,memo)

    
    def __climbStairs(self,i, n, memo):
        #print(memo)
        
        if i > n :
            return 0
        
        if i == n:
            return 1
        
        if memo[i] > 0:
            return memo[i]
        
        memo[i] = self.__climbStairs(i+1,n, memo) + self.__climbStairs(i+2,n, memo)

        
        return memo[i]

 

계산값을 memo 배열에 담아둔다.

이후 이미 계산된 값이 있으면(memo[] > 0) 재귀호출을 또 하지 않고, memo 배열의 값을 사용한다. 중복호출을 막는다.

 

시간복잡도 : O(N)

• 재귀호출 N번함 (중복호출 안 함)

공간복잡도 : O(N)

• memo 배열이 추가로 필요하다 O(N) + 재귀호출을 N번 한다 O(N)

 

3. 재귀호출 memo 활용 (top down 방식)

class Solution:            
            
    def climbStairs(self, n: int) -> int:
        
        # memo[i] :
        memo = [0]*(n+1)
        memo[1] = 1
        if n>=2 :
            memo[2] = 2
        return self.__climbStairs(n,memo)

    
    def __climbStairs(self,i,memo):
        if memo[i] > 0 : #이미 호출됐던 경우, memo에 저장된 값을 사용함 (중복호출x)
        	return memo[i]
        
        memo[i] = self.__climbStairs(i-2,memo) + self.__climbStairs(i-1,memo)

        
        return memo[i]

 

시간복잡도 : O(N)

재귀호출 N번함 (중복호출 안 함)

공간복잡도 : O(N)

memo 배열이 추가로 필요하다 O(N) + 재귀호출을 N번 한다 O(N)

 

참고링크

kylejung0828.github.io/algorithm/climbing-stairs/

[알고리즘] Leetcode 70. Climbing Stairs (Easy) 풀이