.leetcode(70. Climbing Stairs)

문제

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

Climbing Stairs - LeetCode

문제 풀기 전

1. dp냄새가 난다. 이전것을 기억해서 풀어야 겠다.
2. 방법이 2개(step을 1개 가냐 2개 가냐)닌깐 1일때 recursion, 2일때 recursion하면 될거같다.
3. 2개의 방법으로 n개씩 도달하니 O(n)걸릴것이다.

직접 푼 풀이

소요시간: 14분(09:07 ~ 09:21)

class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }

        int[] cache = new int[n];
        for (int i=0; i<n; i++) {
            cache[i] = -1;
        }

        return recursion(n, cache);
    }

    public int recursion(int n, int[] cache) {
        if (cache[n-1] != -1) {
            return cache[n-1];
        }

        if (n == 1) {
            return 1;
        }  else if (n == 2) {
            return 2;
        }

        int cnt = 0;
        cnt += recursion(n-1, cache);
        cnt += recursion(n-2, cache);

        return cache[n-1] = cnt;
    }
}

느낀점

1. 제약사항보면 n이 1보다 크다고 했는데 괜한 사족 if(n==0)을 달았다. 제약사항을 먼저 확인한자.
2. 처음에는 캐쉬없이 구현을 진행했다. 그러니 바로 Time Limit Exceeded 가 발생했다.
3. 그래서 캐쉬 배열을 생성해서 초기화한 후에 결과가 생성될때마다 저장하도록 해두었다. 이건 솔루션을 통해보니 recursion with memory이라고 한다. dp는 해당 문제를 작은 문제로 쪼갤 수 있는데 그 방식은 아래와 같다.
4. dp풀이를 한번 더 보면 작은문제에서 전체문제로 값이 도출되는데 꼭 필요한게 저런 공식과 초기화 그리고 제한사항인거 같다.
5. 또 다른 풀이는 dp에서 조금 더 생각해볼 수 있다. dp에서의 공식을 보면 피보나치 수열임을 알 수 있다. 이 문제는 결국 값을 구하는 문제이기때문에 피보나치로만도 문제를 해결할 수 있다. 피보나치는 앞의 두수를 더 해 다음수를 만드는데 따라서 dp처럼 배열을 쓰지 않고 공간을 절약할 수 있다.
6. 피보나치를 풀이하는 방식이 일반적으로 덧셈을 이어가는 거 외에 2개나 더있다. 효과는 시간을 log로 줄일 수 있다는 것이다. 하나는 행렬을 이용하는거고 또 하나는 피보나치 공식이 있는데 그걸 그대로 적용하는 방식이다. 공식에는 pow함수가 들어가는데 그때 log의 시간이 걸린다. 위의 방식은 나중에 다시 한번 풀어보자.

솔루션 공부 후 추가로 푼 풀이

#dp를 이용한 풀이
class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } 

        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i=3; i<=n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

누적되는 알고리즘 접근 설명서

1. 제한값이 있는지 확인한다.

2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.

3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.

4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.

5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.

6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.

7. TreeNode는 left,right,val으로 구성해볼 수 있고 ListNode는 val,next로 구성해볼 수 있다.

8. ListNode문제가 나오면 꼭 그림으로 next관계를 이해해보자. 그리고 기존의 데이터를 이용해서 이어잘라붙이기에 대한 시도도 꼭 해보자.

9. 배열에서 갯수를 센다고 하면 Brute force, HashMap, Sorting방법을 생각해보자.

10. 만약에 대다수를 구하는 문제라면 Boyer–Moore majority vote algorithm를 생각해보자.

11. Arrays 디버깅할때 Arrays.stream(nums).boxed().forEach(System.out::println);하면 결과를 볼수 있다.

12. 순서, 부호를 이용해서 공간을 절약할 수 있는지 생각해본다.

13. 간단한것 부터 생각해본다. 배열이 있다면 인덱스를 양방향으로 사용하기보다는 한방향으로 사용해보고 정안되면 양방향으로 생각을 바꿔보자. 간단하게 생각하고 간단하게 문제를 만들줄 알아야한다.

14. 값을 원하는지 요소를 원하는지 확인해라. 일반적으로 값을 구하는게 더 간단하게 풀 수 있다.

15. dp라고 생각되면 꼭 캐쉬를 염두해두자. dp로 풀때는 큰문제를 작은문제로 쪼갤 수 있다는 것이고 그런게 보이면 조건, 초기화, 공식에 대해 한번 확인해보자.

나중에다시한번

• 피보나치의 시간복잡도를 줄이기 위해서는 행렬로 접근하는 방식이 있다. 피보나치 수열을 일반적으로 계산했을때는 n의 시간복잡도인데 행렬을 이용하면 logN의 시간이 걸린다.