문제접근
문제 : LeetCode 70. Climbing Stairs (https://leetcode.com/problems/climbing-stairs/description/)
1) 1칸과 2칸의 조합으로 n칸을 올라야 함
2) n칸 오르는 방법
: (n-1)칸을 오르고 + 1칸 오르기
: (n-2)칸을 오르고 + 2칸 오르기
3) n=1 -> 1, n=2 -> 2
제출코드
class Solution {
public:
int climbStairs(int n) {
int result = 0;
if (n == 1) return 1;
if (n == 2) return 2;
int s1 = 1, s2 = 2, s3;
for (int i = 2; i < n ; i++) {
s3 = s1 + s2;
s1 = s2;
s2 = s3;
}
return s2;
}
};문제 해결
- 재귀함수 시간복잡도 문제
처음에는 f(n) = f(n-1) + f(n-2) 형태의 단순 재귀함수로 문제를 구현하였다. 그러나 이 방식은 동일한 계산을 반복적으로 수행하게 되어 시간복잡도가 O(2ⁿ)으로 매우 비효율적이다.
이를 해결하기 위해 재귀 호출 대신 변수를 사용하여 값을 직접 저장하고 누적하는 방식으로 중복 계산을 방지하였다. n = 1, n = 2일 때의 base case를 기준으로, n > 2인 경우에는 반복문을 통해 직접 값을 더해가며 계산하였다.
이 방식은 반복문을 한 번만 수행하므로 시간복잡도는 O(n)으로 효율적이다.
오늘의 회고
시간복잡도를 고려하여 구현하기.
