리트코드 - 70. Climbing Stairs

리트코드 - 70. Climbing Stairs

출처 - https://leetcode.com/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

계단을 올라가고 있습니다. 꼭대기에 도달하려면 n개의 단계가 필요합니다.

각 단계에서는 1단계 또는 2단계씩 올라갈 수 있습니다. 꼭대기에 도달하기 위해 몇 가지 서로 다른 방법으로 계단을 올라갈 수 있을까요?

 

의사코드

climbStair (int n)     if (n <= 2)         n 리턴     stepSum 배열 생성(n+1 크기만큼)     stepSum[1] = 1     stepSum[2] = 2     recursive(n, stepSum) 리턴 함수 recursive(n, stepSum)     if (stepSum[n] == 0)       stepSum[n] = recursive(n - 1, stepSum) + recursive(n - 2, stepSum)    stepSum[n] 리턴

 

풀이코드

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] stepSum = new int[n + 1];
        stepSum[1] = 1;
        stepSum[2] = 2;

        return recursive(n, stepSum);
    }

    private int recursive(int n, int[] stepSum) {
        if (stepSum[n] == 0) {
            stepSum[n] = recursive(n - 1, stepSum) + recursive(n - 2, stepSum);
        }
        return stepSum[n];
    }
}

 

코드설명

DP를 이용한 문제이다.

큰 문제를 잘개 쪼개서 리프노드와 같이 제일 끝에서 계산결과를 점점 더해 상위로 올라가야 한다.

 

먼저 1번째 계단을 오르는 경우의 수는 1가지 이다.

다음으로 2번째 계단을 오르는 경우의 수는 1 + 1, 2 2가지이다. 아직까지는 규칙이 없다.

 

3번째 오르는 계단을 오르는 경우의 수는?

1 + 1 + 1

2 + 1

1 + 2

3가지이다.

 

이것은 다시 이렇게 분류할 수가 있다.

마지막을 한 칸 올라가는 경우

(1 + 1) // + 1

(2) // + 1

 

마지막을 두 칸 올라가는 경우

1 // + 2

 

그림으로 설명해보면,

올라갈수 있는 칸 수는 1칸과 2칸이므로, 2층에서 한 칸 올라가는 방법과, 1층에서 2칸 올라가는 방법 두 가지 뿐이다.

 

1층에서 두 칸 올라갈 수도 있지 않느냐?한다면 그건 2칸까지 가는 방법에서 이미 계산이 되어있다.

이미 2층까지 가는 계산에서 품고 있기 때문에 3층까지 가는 경우는 1칸씩 올라간 경우, 2칸씩 올라간 경우만 고려하면 된다.

따라서

3층까지 올라가는 경우의 수 = 1층까지 올라가는 경우의 수 + 2층까지 올라가는 경우의 수

가 된다.

 

이를 재귀적으로 recursive 메소드에 구현해 놓았다.

DP의 핵심은 앞에 저장한 값을 다시 계산하지 않는 것이기 때문에,

규칙이 없는 값을 미리 저장해놓고(배열의 1과 2) 저장된 값을 가져오고 있다는 것이 중요하다.

연산된 결과가 동일할 때, 이렇게 미리 저장해놓는 것을 메모이제이션(memoization)이라고 한다.

 

시간복잡도 - O(n)

공간복잡도 - O(n) (n+1 개의 배열이므로)

 

문제를 풀며 생각한 흐름과 배운 점

요즘 기업 코테를 보면 막히는 문제들이 이 DP문제들이다.

이름은 동적 프로그래밍이라서 행위에 있어서는 계속 다른 값을 구하는 동적 프로그래밍이지만, 동작에 있어서는 계산된 값을 사용한다는 것이 더 중요한 것 같다.

 

이번 문제는 간단한 1D DP문제이지만 이 문제를 풀어내는 핵심을 파악하도록 계속 풀어봐야겠다.

 

정리

1차원 동적 프로그래밍 방식으로 값을 계산하는 방법