[LeetCode] 70. Climbing Stairs - DP, 피보나치 수

오늘의 학습 키워드

DP, 피보나치 수열

 

알고리즘 문제

• LeetCode - Easy
• 70. Climbing Stairs

https://github.com/dev-jinius/Algorithm-Practice/tree/main/LeetCode/0070-climbing-stairs

Algorithm-Practice/LeetCode/0070-climbing-stairs at main · dev-jinius/Algorithm-Practice

 

---

 

오늘의 회고

1. 문제를 보고, 어떤 자료구조를 사용해서 어떻게 풀어야 할 지 생각이 들었나?

2. 생각이 들었다면, 얼마나 시간이 소요되었나?

2. 생각이 들지 않았다. 다시 문제를 파악하고, 해당 자료구조와 알고리즘을 더 정확히 습득해야한다.

 

3. 시간복잡도

4. 다른 방법으로 풀 수 있는 방법은 고민해봤나?

 

---

공부했던 내용

피보나치 수열

• 특징
  • f(n) = f(n-1) + f(n-2)
  • 반복적인 패턴과 중복되는 부분이 있는 경우 유용하다.
  • 주로 연속된 선택에서 이전 결과를 활용해야하는 경우 생각해보면 좋다.
• 느낀점
  • 목표(최종 결과)를 먼저 생각하고, 목표를 달성하기 위해 어떻게 도달할 수 있는지 생각해보는 게 우선인 것 같다.
  • 즉, Top-Down 방식의 사고로 접근하면 좋겠다.
  • DP를 같이 사용하면 좋은 점은 피보나치 수열의 반복적인 계산을 DP를 통해 줄일 수 있다. 
  • DP는 각 계산 결과를 저장해두고 재사용할 수 있다. ( Memoization, 메모이제이션)

 

DP (Dynamic Programming, 동적계획법)

• 특징
  • 최적화 문제를 효율적으로 해결하기 위해 사용되는 방법
  • 특정 문제를 하위 문제로 분할하여 해결하고, 이 하위 문제들의 결과를 저장해 중복 계산을 줄이는 기법이다.
• 메모이제이션 (Memoization)
  • 주어진 문제를 해결할 때 중간 결과를 저장하는 방식으로, 주로 재귀와 함께 사용하여 Top-Down 접근 방식.
• 타뷸레이션 (Tabulation)
  • 작은 하위 문제부터 차례로 계산해 나가며 상위 문제를 해결하는 방식으로, Bottom-Up 접근 방식.
  • 반복문을 사용하여 순차적으로 계산한다.

---

지난 회고

처음 시도

• 처음에는 재귀로 현재 숫자에 +1 하는 재귀와 +2 하는 재귀를 만들었다.
• 테스트 케이스에서는 성공했지만, Submit하니 시간초과로 실패했다. => 효율성 문제
• 시간복잡도는 O(2^n) => 2가지 경로(+1칸, +2칸)를 계속해서 탐색하므로 두가지씩 분할하면서 n이 커질수록 트리 노드 수가 급격히 증가한다.

class Solution {

    int ways;

    public void recur(int top, int current) {
        if (current == top) {
            ways++;
            return;
        }
        if (current > top) {
            return;
        }
        if (current < top) {
            recur(top, current+1);
            recur(top, current+2);
        }
    }

    public int climbStairs(int n) {
        this.ways = 0;    

        recur(n, 0);

        return ways;
    }
}

해결

• 피보나치 수열 이용
  • 처음에 이해하지 못해서 노트에 몇 번을 끄적여봤다. 왜 피보나치 수열이지? 왜 1번째 계단 경우의 수 + 2번째 계단 경우의 수가 3번째 계단 경우의 수가 나오는거지?
  • 이 문제는 +1칸, +2칸 오를 수 있는 조건이 있다 => 패턴 OK
  • 1번째 계단을 오르려면 => 바닥에서 +1칸
  • 2번째 계단을 오르려면 => 1번째 계단에서 +1칸, 바닥에서 +2칸
  • 3번째 계단을 오르려면 => 2번째 계단에서 +1칸, 1번째 계단에서 +2칸
  • 4번째 계단을 오르려면 => 3번째 계단에서 +1칸, 2번째 계단에서 +2칸
  • N번째 계단을 오르려면 => N-1번째 계단에서 +1칸, N-2번째 계단에서 +2칸
  • 그런데 왜 경우의 수를 합치는 걸까? 이해가 안됐었다..
    • => 3번째 계단 경우의 수로 예를 들면,
    • 2번째 계단 오르는 경우 (1칸 + 1칸, 0 + 2칸) : 2가지 경우의 수
      • -> 여기서 각각 +1칸하면(1칸 + 1칸 + 1칸, 0 + 2칸 + 1칸) 3번째 계단이 된다.
    • 1번째 계단 오르는 경우 (0 + 1칸) : 1가지 경우의 수
      • -> 여기서 +2칸하면(0 + 1칸 + 2칸) 3번째 계단이 된다.
    • 즉, 3번째 계단 경우의 수는 2번째 계단 오르는 경우의 수 + 1번째 계단 오르는 경우의 수와 같다. 

class Solution {

    public int climbStairs(int n) {
        if (n <= 2) return n;

        int a = 1; 
        int b = 2;
        int result = 0;

        for (int i = 3; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;    
        }

        return result;
    }
}

---