[Top Interview Questions] 70. Climbing Stairs

정답)

class Solution:
    def climbStairs(self, n: int) -> int:
    	# 동적 계획법
    
    	# 바텀업 DP 테이블
        dpTable = [1, 1]

        for i in range(n-1):
            # 테이블에 n-1, n-2번째 피보나치 숫자들을 더해 추가
            dpTable.append(dpTable[-1] + dpTable[-2])
        
        return dpTable[-1]

 

참고자료:

NeetCode, 앎의 공간

문제)

문제출처

정상까지 n번 만큼 걸어야되는 계단이 있습니다. 

 

이 계단을 오르기 위해서 한번에 1번 또는 2번의 걸음으로 오를 수 있습니다.

총 몇가지의 방법으로 이 계단을 오를 수 있습니까?

 

예시 1)

n = 2

output = 2

1. 1+1

1. 2

 

예시 2)

n = 3

output = 3

1. 1+1+1

2. 1+2

3. 2+1

 

제한)

1 <= n <= 45

풀이)

기본원리)

피보나치의 원리를 사용할 것입니다. (왜 피보나치인지는 나중에...)

 

리스트에 F0, F1의 값인 1을 먼저 추가해 줍니다.

 

그리고 F2부터 Fn까지 피보나치의 원리를 사용하여 리스트에 추가해줍니다.

 

마지막에 리스트의 -1번째 숫자를 리턴합니다.

왜 피보나치)

제가 이 문제를 처음 접근했을 때는 binary tree를 사용할 생각 이었습니다.

 

각 노드의 child node들을 만들어 줄 때 1 혹은 2를 더하여 구하고자 하는 n이 나오는 줄기들의 개수를 리턴하는 원리를 생각했습니다.

 

하지만 직접 코드를 짜려고 하니 막막해져 NeetCode의 영상을 봤더니 이진트리 (binary tree)를 사용하게 되면

이미 구한 정답을 다시 계산하는 과정이 꽤나 반복되어 시간 복잡도가 너무 커진다고 하더군요.

 

각 트리에 같은 연산이 반복

그래서 저희는 필요한 정보들이 있는 한 줄기만 보겠습니다.

 

필요한 정보가 있는 첫번째 줄기를 확인

위 줄기에서 각 노드마다 그 노드를 포함하여 몇 개의 정답이 존재하는지 확인하겠습니다.

줄기의 노드와 그 노드를 포함한 아래에 몇개의 초록색 삼각형이 있는지 봐주세요. 

 

각 트리 아래 몇개의 정답이 존재하는지 확인

노드가 5일 경우에는 정답이 1개.

노드가 4일 경우에도 정답이 1개.

노드가 3일 경우에는 정답이 2개.

노드가 2일 경우에는 정답이 3개.

노드가 1일 경우에는 정답이 5개.

노드가 0일 경우에는 정답이 8개. 

 

패턴이 보이시나요?

피보나치의 수열입니다. 

 

피보나치의 수열을 이용하여 정답을 구함

인덱스와 숫자가 혼용되어서 조금 헷갈리실 수도 있지만 n개의 계단을 올라가는데 총 몇 가지의 수가 존재하는 지 구할 때 피보나치가 사용된다 라는것을 이해하시면 되겠습니다.

이제 코딩으로)

먼저 피보나치 수열의 기본정보 F0, F1의 값을 dp테이블에 저장해줍니다.

 

def climbStairs(self, n: int) -> int:
        dpTable = [1, 1]

피보나치 수열)

2보다 큰 n번째 피보나치 숫자들을 구할 때는 아래의 식을 사용합니다.

 

Fn = Fn-1 + Fn-2

 

그리고 n-1과 n-2는 dpTable의 맨 뒤 두 숫자 입니다.

 

그러므로 dpTable의 -1번째 -2번째 원소들을 더하여 2부터 n까지의 피보나치 숫자들을 구해 리스트에 차례대로 추가해줍니다.

 

0부터 n까지의 피보나치 수열을 구했다면 최종값인 dpTable의 -1번째 숫자를 리턴해줍니다.

이 리턴되는 숫자는 n개의 계단에서 올라갈 수 있는 방법의 총 갯수입니다.

 

def climbStairs(self, n: int) -> int:
        dpTable = [1, 1]

        for i in range(n-1):
            dpTable.append(dpTable[-1] + dpTable[-2])
        
        return dpTable[-1]

디버깅)

n = 5

 

dpTable = [1, 1]

 

(i=0)

[1, 1, 2]

 

(i=1)

[1, 1, 2, 3]

 

(i=2)

[1, 1, 2, 3, 5]

 

(i=3)

[1, 1, 2, 3, 5, 8]

 

return 8    # 계단의 개수가 5개인 계단에서는 총 8가지의 방법으로 계단을 오를 수 있습니다.

 

 

이번 문제도 패턴을 파악하는게 중요했던 것 같습니다.

피보나치의 수열을 사용한다는 것을 알았더라면 혼자서도 풀었겠죠?

다음부터는 예시 몇개를 사용해서 풀어봐야겠습니다 ㅎㅎ

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)