반응형
1. 문제
https://leetcode.com/problems/climbing-stairs/description/
2. 코드
처음 짠 코드) 타임 아웃
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let count = 0;
const climb = (total) => {
if(total === 0) count++;
else{
if(total - 1 >= 0)
climb(total-1);
if(total - 2 >= 0)
climb(total-2);
}
}
climb(n);
return count;
};
정답)
이 문제는 피보나치를 활용하여 풀면 시간 복잡도를 줄일 수 있다.
예를 들어 계단을 4번 오르는 데에는 총 5가지 방법이 있다.
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
계단을 3번 오르는 데에는 총 3가지 방법이 있다.
1 1 1
1 2
2 1
계단을 2번 오르는 데에는 총 2가지 방법이 있다.
1 1
2
계단을 4번 오르는 방법에 2번과 3번 오르는 과정이 중복된다. 그래서 피보나치를 통해 이전 값을 메모이제이션해두면 시간 복잡도를 줄 일 수 있게 되는 것이다.
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n < 4) return n;
let fib = [1, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
};
반응형
'리트코드 > easy' 카테고리의 다른 글
[리트코드] 14. Longest Common Prefix - js (0) | 2023.09.06 |
---|---|
[리트코드] 2806. Account Balance After Rounded Purchase - js (0) | 2023.09.05 |
[리트코드] 205. Isomorphic Strings - js (0) | 2023.09.02 |
[리트코드] 121. Best Time to Buy and Sell Stock - js (0) | 2023.08.29 |
[리트코드] 20. Valid Parentheses - js (0) | 2023.08.23 |