자바 코딩테스트
리트코드 70. Climbing Stairs
백엔드 개발자
2025. 4. 7. 22:36
계단을 오르는데, 총 n개의 계단을 올라야 한다.
각각 한번에 1개또는 2개의 계단만 올라갈 수 있다.
계단을 올라갈 수 있는 경우의 수는 몇개나 될까?
n이 2이면
1. 1 +1
2. 2 로 2개.
n이 3이면
1 1 1
12
21로 3개
n이 4면
1111
112
121
211
22
총 5개
n이 5면
11111
1112
1121
1211
2111
122
212
221
총 8개
1, 2, 3, 5, 8,
0 1 2 3
n이 3이상일때
f(n) = f(n-1) +f(n-2)
f(1) = 1
f(2) = 2
f(3) = 3
1번째 풀이 방법
전형적인 피보나치 수열인거 같아서 1,2의 값은 바로 구하고,
그다음에는 재귀 함수를 이용해서 풀었다.
class Solution {
public int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
}
그러나 시간초과가 났다..
2. 메모이제이션
피보나치를 푸는 방법을 검색해보니
메모이제이션이라는 방법이 있었다.
없는 값은 계산하고, 있는 값은 이전 것을 사용하는 방식이다.
시간복잡도도 O(n)이면서 재귀보다는 빠르므로. 재귀는 2^n이었다.
그러니까, arrayList를 만들어서 (arrayList는 조회속도가 LinkedList보다 빠르니까 선택했다)
없으면 add 하고, 있으면 get으로 가져오는 것이다.
다만 1,2의 경우 있는 값을 사용하지 않으면 에러가 나므로 3이상으로 제한해서 풀었다.
public class Solution {
private List<Integer> list = new ArrayList<>(Arrays.asList(1, 2)) ;
public int climbStairs(int n) {
if (n >= 3 && list.size() < n) {
list.add(n - 1, climbStairs(n - 1) + climbStairs(n - 2));
}
return list.get(n - 1);
}
}
3. 바텀업 방식
아예 아래서부터 계산하면서 더하는 방식도 있었다.
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
for (int i = 2; i < n; i++) {
list.add(list.get(i-1)+list.get(i-2));
}
return list.get(n-1);
}
탑다운은 점화식을 이해하기 쉽다.
바텀업은 재귀호출을 안해서 시간과 메모리 사용량을 줄일 수 있는 장점이 있다고 한다.