코테

99클럽 코테 스터디 8일차 TIL + [LeetCode 70번] Climbing Stairs

pipinstall 2025. 4. 7. 23:08

오늘의 학습 키워드

  • 동적 프로그래밍(Dynamic Programming)
  • 피보나치 수열 패턴

[LeetCode 70. Climbing Stairs 문제]

문제 요약

  • n개의 계단을 오르는 방법을 구하는 문제
  • 한 번에 1계단 또는 2계단씩 오를 수 있음
  • 꼭대기까지 오르는 서로 다른 방법의 총 개수를 구해야 함

해결 방법

핵심은 이 문제가 피보나치 수열의 패턴을 따른다는 점을 인식하는 것이고.

n번째 계단에 도달하는 방법의 수는 (n-1)번째 계단과 (n-2)번째 계단에 도달하는 방법의 수의 합과 같다.

알고리즘:

  1. 기본 케이스: 1계단은 1가지 방법, 2계단은 2가지 방법
  2. result = n-1 + n-2
  3. n에 대한 답을 구할 때까지 계산

Java 코드 구현 (반복문 사용)

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int first = 1;  // 첫번째 계단
        int second = 2; // 두번째 계단
        int result = 0;
        
        for (int i = 3; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        
        return result;
    }
}

오늘의 회고

What?

처음에는 문제를 단순하게 생각해서 n을 반환하는 식으로 접근했으나. 

실제로는 피보나치 수열 패턴을 사용한 문제였다.

How?

방법을 몰라서 구글링을 통해 진행했다,, 

 

Point?

  1. 수학적 패턴을 찾으면 효율적으로 해결할 수 있다는 것을 알게 되었다.
  2. 문제를 잘 해석 또는 이해 하는게 중요하다는것을 다시 깨닫게 되었다.
  3. 익숙해지려면 비슷한문제를 많이 풀어야한다,,