오늘은 70. Climbing Stairs문제를 풀었다.
처음엔 단순해 보였는데, 의외로 많은 함정이 있었다.
❌ 첫 번째 삽질: 패턴 인식만 했을 뿐
처음에 문제를 보고 각 케이스를 하나씩 계산해보기 시작했다.
f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 5
f(6) = 8
이 숫자들을 보다가 문득 깨달았다.
"어? 피보나치 수열이잖아!"
각 숫자가 바로 앞의 두 숫자의 합으로 이루어진 수열이었다. 고등학교 수학 시간에 배웠던 그것!
그런데 문제는, 이걸 어떻게 코드로 구현해야 할지 전혀 감이 오지 않았다. 왜인지 자꾸 배열이나 리스트로 연결해서 생각하려고 했다. 계속 여기서 막혔다.
"이 수열을 배열에 저장해서 앞의 두 값을 참조하면 되지 않을까?"
"인덱스로 접근을 해야할까?"
왜 자꾸 이런 식으로만 생각했는지 모르겠다. 결국은 인터넷의 도움을 구했다... 꼭 암기해야지.
🔍 해결 방법 탐색: 재귀적 접근
찾아보니 생각보다 너무 간단했다. 고등학생 때 배웠던 함수식 그대로 구현하면 되는 것이었다:
이걸 재귀 함수로 그대로 구현하면:
func climbStairs(_ n: Int) -> Int {
if n <= 0 {
return 0
}
if n == 1 {
return 1
}
return climbStairs(n - 1) + climbStairs(n - 2)
}이렇게나 직관적인 코드였다! 호기롭게 제출을 눌렀는데...
💥 두 번째 삽질: 시간 초과
제출 결과는 실패... 시간 초과(Time Limit Exceeded)라는 오류가 떴다.
시간 복잡도를 확인해보니 O(2^n)이었다. 왜 이렇게 비효율적인지 이해가 안 됐다.
자세히 살펴보니, 재귀 함수가 같은 계산을 엄청나게 중복해서 한다는 것을 알게 됐다.
예를 들어:
fibonacci(5)를 계산할 때:
fibonacci(4) + fibonacci(3)을 계산
fibonacci(4)를 계산할 때:
fibonacci(3) + fibonacci(2)를 계산
fibonacci(3)을 계산할 때: <-- 여기서 중복!
fibonacci(2) + fibonacci(1)을 계산
...
같은 fibonacci(3)을 여러 번 계산하게 되는 것이다. n이 커질수록 이 중복 계산은 기하급수적으로 늘어난다.
✅ 최적화된 해결책: 반복문 사용
결국 반복문을 사용하는 해결책을 찾았다:
func climbStairs(_ n: Int) -> Int {
if n <= 0 {
return 0
}
if n == 1 {
return 1
}
if n == 2 {
return 2
}
var a = 1
var b = 2
var result = 0
for _ in 3...n {
result = a + b
a = b
b = result
}
return result
}이 방법은 각 숫자를 딱 한 번만 계산하므로 시간복잡도가 O(n)이다. 앞의 두 값만 기억하면서 진행하니 공간복잡도도 O(1)로 매우 효율적이다.
⚠️ 재귀와 반복문의 차이
재귀 함수는 코드가 간결하고 직관적이지만, 중복 계산 문제로 인해 피보나치 같은 경우에는 성능이 매우 나쁘다.
반면 반복문은 코드가 조금 더 복잡해 보일 수 있지만, 각 값을 한 번만 계산하므로 훨씬 효율적이다.
이번 문제를 통해 "모든 재귀는 반복문으로 변환할 수 있다"는 것을 다시 한번 깨달았다.
💡 오늘의 교훈
- 문제 패턴을 빨리 파악하는 것은 중요하다. 이것이 피보나치 수열임을 알아차린 것은 잘한 일이다.
- 수학적 개념을 코드로 변환하는 능력을 기르자. 수식을 그대로 코드로 옮기는 사고방식이 필요하다.
- 항상 시간복잡도를 고려하자. 단순히 동작하는 코드가 아니라 효율적인 코드를 작성해야 한다.
- 재귀와 반복문의 장단점을 이해하자. 상황에 맞는 적절한 방법을 선택하는 것이 중요하다.
사실 나의 힘으로 온전히 한 건 이게 피보나치 수열이구나 라고 깨달은 사실 빼고는 없다. 좀 부끄럽지만, 알고리즘 구현 방법을 제대로 알지 못했다는 것을 인정하고 더 공부해야겠다.
모레에 꼭 복습을 해야겠다. 아니면 다른 피보나치 관련 문제를 더 풀어봐야겠다.
