[LeetCode] Climbing Stairs

문제 링크

Can you solve this real interview question? 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 can you climb to the top? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Constraints: * 1 <= n <= 45

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

문제 요구 조건

n개의 스텝을 올라갈 수 있는데, 한 번에 1 또는 2 스텝씩 올라갈 수 있다.

n도달할 수 있는 모든 경우의 수의 갯수를 구하라

나의 문제 풀이

문제 못풀었어요 ㅠ 답을 봐도 왜 이렇게 푸는지 이해가 안되서 1시간동안 이게 도대체 무슨 말인지 이해해보려 노력했어요. 그 결국 어떻게 이해를 하게 되었는지, 또 어떻게 쉽게 이해해볼 수 있을지에 관해서 말씀드리도록 할게요.

정답 문제 풀이

일단 몰라서 답안을 보게 되면, 마지막 계단을 오른 경우의 수를 생각해보라고 해요. 그럼 당연히 한 번에 오를 수 있는 계단의 수는 1 또는 2 밖에 없죠. 그리고 n-1계단에 도달한 경우와 n-2계단에 도달한 경우의 수를 더하면 마지막 계단에 도착하는 경우의 수가 된다고 해요.

GPT의 답변

JavaScript

계단 오르기 문제 쉽게 이해하기 🪜
이 문제는 복잡하게 생각할 필요 없이, 단순히 경우의 수를 세는 문제예요.

핵심 아이디어는 이거예요:
n개의 계단을 오르는 방법의 수는, 
n−1번째 계단에 도착해서 마지막 한 칸을 오르는 방법의 수와, 
n−2번째 계단에 도착해서 마지막 두 칸을 오르는 방법의 수를 더한 것과 같아요.

예를 들어, 4번째 계단을 오르는 방법을 생각해볼게요.

3번째 계단에서 한 칸 오르기: 
3번째 계단에 도착하는 모든 방법의 수만큼 4번째 계단에 도착하는 방법이 생겨요.

2번째 계단에서 두 칸 오르기: 
2번째 계단에 도착하는 모든 방법의 수만큼 4번째 계단에 도착하는 방법이 생겨요.

따라서 (4번째 계단 방법) = (3번째 계단 방법) + (2번째 계단 방법) 이 되는 거죠.

여러분은 이 말이 이해가 되시나요? 이해가 되시는 분은 엄청 똑똑한 분이실거라 생각해요. 하지만 저 같은 분들이 훨씬 많을 것이라고 생각하기 때문에 좀 더 풀어보도록 할게요.

저만의 풀이 재해석

먼저 답을 봐도 무슨 말인지 이해를 못했어요. 제일 이해가 되지 않은 것은 5번째 계단이 마지막 계단이라고 가정했을때 4번째 계단에서 오르는 방법과 3번째 계단에서 오르는 방법의 총합이 5번째 계단을 오르는 방법이 되는가 였어요.

왜냐하면 숫자가 많아질수록 그 두 방법이 겹치지 않는다고 어떻게 확신할 수가 있지?? 라는 생각이 들었죠.

하지만 모든 경우의 수를 병렬로 나열하고 답안의 의미를 보니 이제 좀 이해가 되는 것 같았어요. 마지막 계단에서 1스텝으로 도달하는 경우의 수와 2스텝으로 도달하는 경우의 수가 겹치지 않는다는 것이였죠.

이 문제가 어려운 것은 바로 이 마지막 스텝 종류의 경우의 수는 겹치지 않는다 라는 것을 직관적으로 떠올리기 힘들기 때문에 어려운 거였어요.

이 지식에서부터 문제를 풀어갈 수가 있어요.

피보나치 수열

위의 예시를 따라서 5번째 계단을 오르는 경우의 수는 4번째 계단의 경우의 수와 3번째 계단의 경우의 수의 합이 되는 것이죠. 그리고 이것을 목표값이 나올 때까지 앞의 두수를 더해서 그 다음수를 구하는 코드를 작성하면 되는 것이죠. 사실 이 방식으로 나열된 수의 배열을 피보나치 수열로 많이 알려져 있어요.

그럼 이제야 이 문제를 왜 다음 코드처럼 풀었는 지 이해가 되실거에요.

정답 코드

JavaScript

var climbStairs = function(n) {
    if (n <= 2) {
        return n;
    }

    let a = 1;
    let b = 2;

    for (let i = 3; i <= n; i++){
        const temp = a + b;
        a = b;
        b = temp;
    }

    return b;
};

문제 풀이의 과정은 다음과 같아요.

1과 2는 그대로 반환해도 해주면 되겠죠? 1에 도달하는 방법은 1이고, 2에 도달하는 방법은 2가지이니까요. 그리고 피보나치 수열의 다음 수를 구하기 위해서 앞의 두수가 필요하다는 필요 조건도 만들어 줄 수 있게 되어요.

a / b로 앞의 두수를 세팅을 해주세요.

그래서 for문의 시작점을 3부터 설정할 수 있게 되는 것이죠.

두 수를 더한 다음 값을 temp로 선언하고

b를 a로 할당하고, 더한값을 다시 b로 할당하여서 n값이 나올때 까지 순회하면 되는 거에요.

느낀점

솔직히 문제자체가 어렵게 느껴지지 않았는데, 이걸 코드로 만들려니 정말 어렵게 느껴지네요. 그리고 이런 문제를 직관적으로 푸실수 있는 분이 얼마나 될지도 궁금하네요. 저는 그냥 많이 풀어봐야 될 것 같아요.

오늘도 글 읽어주셔서 감사해요 다음에 또 뵈어요!