Day-03. DP와 함께 계단 오르기

매우 간단한 DP 문제 부터 확인해보도록 하겠습니다.

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

 

한번에 1개 혹은 2개의 계단만 오를 수 있다고 가정할때, 총 N개의 계단을 올라갈 수 있는 가지수를 구하는 문제입니다.

아무리 문제만 바라보고 있어도 뾰족한 수가 떠오르지 않으니 가능한 방법들을 노트에 직접 구해보았습니다. 머리가 스마트 하지 않으면 손과 발이 고생이라라던 옛 현인들의 말씀이 순간 떠오르는 군요. 언젠가는 조금이라도 스마트해진 브레인이 되길 바라는 마음에 맘 굳게 먹고~!

 

모두 다 해버리겠어!

S1 = 1	S2 = 2	S3 = 3	S4 = 5	S5 = 8	S6 = 13
1	1,1 2	1,1,1          2,1            1,2	1,1,1,1        2,1,1          1,2,1 1,1,2 2,2	1,1,1,1,1      2,1,1,1        1,2,1,1 1,1,2,1 1,1,1,2 2,2,1          2,1,2 1,2,2	1,1,1,1,1,1    2,1,1,1,1      1,2,1,1,1 1,1,2,1,1 1,1,1,2,1 1,1,1,1,2 2,2,1,1        2,1,2,1 2,1,1,2 1,2,1,2 1,1,2,2 1,2,2,1 2,2,2

 

 규칙이 보이시나요? S1=1, S2=2, S3=3, S4=5, S5=8, S6=13 즉 Sn = Sn-1 + Sn-2 의 규칙을 갖는 fibonacci 수열임을 알 수 있습니다. 이를 우선 생각나는대로 아래와 같이 코딩해 보았습니다. 보기에도 깔끔하고 음 나름 괜찮게 작성한 것 같습니다. 별 문제 없겠죠 ? 일단 Submit을 눌러봅니다...

class Solution {
public:
    int climbStairs(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

21 hours ago

Time Limit Exceeded

N/A

N/A

cpp

 

 Time Limit Exceeded ?? 수행 시간이 너무 오래 걸리는 코드라서 바로 Fail되었습니다. Time Complexity를 따져 보아야 할 듯합니다. 어림잡아서 tree 맨 아래 쪽 까지 내려간다고 했을때 대략 O(2^n)의 시간이 걸리는 코드였군요. 머리가 스마트하지 않았더니 CPU core가 고생하는군요.

 

 어떻게 하면 수행 시간을 단축 시킬 수 있을까요? 위의 트리를 봐도 중복되는 연산 단계들이 매우 많음을 알 수 있습니다. 이전에 계산했던 값들을 어딘가에 적어두고, 또 계산을 해야 하는 경우 곧바로 읽어 올수 있다면 연산 속도가 줄어들것 같다는 생각이 듭니다. 굳이 영어로 Memoization 이라고 합니다. DP를 공부할때 매우 자주 나오는 용어이죠. DP 알고리즘을 적용하려면 문제에 아래와 같은 특성이 있어야 합니다.

 

• Overlapping Subproblem : 큰 문제를 풀때 작은 문제의 풀이 방법과 동일하게 풀 수 있음
• Optimal Substructure : 작은 문제의 결과 값이 항상 같아야 한다.

 이전 연산 값을 사용하도록 코드를 바꾸어 보았습니다. 뭔가 지저분해 보이지만 계단 N의 가짓수를 구하기 위해, 0번부터 위로 올라가며 계산하는 이런 방식을 Bottom-up 방식이라고 합니다.

class Solution {
public:
    int climbStairs(int n) {
        
        int i=0;
        int prevStep1, prevStep2, prevStep;
        
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        prevStep1 = 1;
        prevStep2 = 2;
    
        for (i=3;i<=n;i++){
            prevStep = prevStep1+prevStep2;
            prevStep1 = prevStep2;
            prevStep2 = prevStep;
        }

        return prevStep;
    }
};

a day ago

Accepted

4 ms

8.3 MB

cpp

 

취향에 따라 아래와 같이 Top-down 형태로 구현도 가능합니다. 계단 N의 가짓수를 구하는 과정을 코드 부분으로 먼저 구현되며, 실행시 N부터 거꾸로 0까지 내려가면서 구한다는 의미로 해석이 가능할듯합니다. 개인적으로는 Top-down이 읽기에는 (readability) 좀더 쉬워 보이지만 항상 recursive function을 사용 할때는 반복을 끝내는 조건을 명확하게 확인해야 합니다. 

class Solution {
public:
    int *array;
    
public:
    int calStairs(int n){
        int steps=0;

        if (n<=2 || array[n]>=0) return array[n];

        steps=calStairs(n-1)+calStairs(n-2);
        array[n] = steps;        
        return steps;
    }
    
    int climbStairs(int n) {
        int result=0;
        array = new int[n+1];
        
        if (n>=0) array[0] = 0;
        if (n>=1) array[1] = 1;
        if (n>=2) array[2] = 2;
        
        result = calStairs(n);
        
        delete[] array;
        array=0;
        
        return result;
    }
};

a few seconds ago

Accepted

4 ms

8.8 MB

cpp

 

 문제의 성격에 따라 다르겠지만 이 예제에서는 실행속도와 사용하는 메모리 공간이 Bottom-up과 Top-down방식이 유사한 결과가 나왔네요.  Bottom-up 코드에서는 변수 2개를 추가로 선언해서 이전 결과값을 저장하면서 반복하며 사용하였습니다. Top-down 코드에서는 recursive function을 내려갈때마다 이전 결과들이 저장되어 있어야 할 것 같아서 동적 array를 사용하였습니다. 메모리 사용 공간 차이가 많이 나겠지했는데, 비슷한 메모리가 사용되네요. 그 차이는 나중에 다시 확인해 봐야 할 듯합니다. (Leetcode에서 말하는 memory usage의 의미가 무엇인지)

 

 c++에서는 'array = new int[n+1];' 처럼 메모리 할당을 한다는 부분을 잠시 눈여겨 보도록 합니다. 동적으로 메모리를 할당했을 때는 꼭 다시 메모리를 회수해야 합니다. 이때 'delete array'가 아닌 'delete[] array'를 사용한 부분도 꼭 확인해 보시기 바랍니다.  코드를 좀더 깔끔하게 정리해야겠지만 조금 지저분한 점 양해를 부탁드립니다.

 

 이번 편도 끝까지 읽어 주셔서 감사합니다. 같이 조금씩 DP 문제들을 더 알아보면서 두뇌를 좀더 Smart하게 연습시켜 보도록 해요~