[ leetcode 문제풀이 ] Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

(Climbing Stairs 문제는 위 링크에서 풀어보실 수 있습니다.)

< Climbing Stairs 문제 설명 >

Climbing Stairs 문제는 다음과 같다.

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways you can climb to the top?

 

한 번에 1계단 혹은 2계단씩 올라갈 수 있다고 할 때 n개의 계단을 올라갈 수 있는 서로 다른 방법의 수는 어떻게 되겠는가?


다음 두 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ n ≤ 45이다.

---

< Climbing Stairs 문제 접근 >

이 문제는 수학의 수열과 점화식 표현 파트에서 대표적으로 접할 수 있는 문제이다. 맨 처음 계단을 오르는 경우를 나누어 생각해보자. 한 번에 1계단 혹은 2계단을 오를 수 있으므로 각각의 경우에 남은 계단의 수는 n-1계단, n-2계단이다.
따라서 n개의 계단을 오르는 방법의 수를 climbStairs(n)이라고 하면

climbStairs(n) = climbStairs(n-1) + climbingStairs(n-2)

임을 알 수 있다.

한편, climbStairs(n)을 재귀적으로 호출하는 과정에서 중복되는 호출은 생기기 마련이다. (ex- climbStairs(6)을 호출하면 climbStairs(6)은 climbStairs(5)와 climbStairs(4)를 호출하는데, climbStairs(5)도 climbStairs(4)를 호출한다) 중복되는 계산으로부터 시간의 낭비를 막기 위해 메모이제이션(memoization)을 사용한다.
메모이제이션은 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 높이는 방법이다.

이를 코드로 나타내면 아래와 같다.(Cpp 사용)

int climbStairs(int n){
    vector<int> cache(n+1);		//메모이제이션을 위해 n+1 크기의 배열 생성
    cache[0] = 1;		//climbStairs(0) = 1로 정의해 계단을 다 올라간 경우를 clear하게 처리
    cache[1] = 1;

    for(int i=2;i<=n;i++)
        data[i] = data[i-1]+data[i-2];		//bottom-up approach
    
    return data[n];
}

 

 

n개의 계단에 대한 결과를 알기 위해서는 반드시 0 ~ n-1개의 계단에 대한 결과를 알아야 하기에 climbStairs(n)에서부터 작은 부분 문제를 호출하는 것이 아닌, 가장 작은 부분 문제에서부터 큰 부분 문제(최종적으로는 climbStairs(n)까지)까지 메모이제이션을 하는 방법(bottom-up approach)을 사용해 코드를 단순화하고 실행 속도를 높였다.