leetcode 70. Climbing Stairs 문제 풀이

문제

https://leetcode.com/problems/climbing-stairs/description/

1차 코드

GPT에게 힌트를 얻어 피보나치 수열 키워드로 1차 코드 작성..!

class Solution {
    func climbStairs(_ n: Int) -> Int {
        switch n {
            case 0: return 0
            case 1: return 1
            case 2: return 2
            default: return climbStairs(n-1) + climbStairs(n-2)
        }
    }
}

‼️ TLE(Time Limit Exceeded) 발생

1. 재귀로 인한 중복 호출
   • 예를들어 climbStairs(4)를 호출하면 climbStairs(3)과 climbStairs(2)가 호출되고, 호출된 climbStairs(3)으로 인해 climbStairs(2)와 climbStairs(1)이 호출됩니다. 이때 climbStairs(2)이 중복으로 호출됩니다. n의 값이 클수록 이런 중복이 기하급수적으로 증가하게 됩니다.
   • 재귀로 인해 climbStairs(n)을 호출할 때마다 매번 climbStairs(n-1)과 climbStairs(n-2)를 호출하고 연속적으로 한 번의 호출 당 두 번의 호출이 발생하게 됩니다.
2. 시간 복잡도 증가
   • 재귀 호출 구조는 피보나치 수열과 동일하기 때문에 시간 복잡도나 **O(2^n)**에 가까워지며, n이 커질수록 시간복잡도 또한 기하급수적으로 증가하게 됩니다. 이로 인해 제한 시간 내 처리가 불가하여 발생한 것으로 예상할 수 있습니다.
3. 스택 오버플로우 발생 가능
   • 함수 호출시 실행 정보를 위해 스택에 저장 공간(스택 프레임)이 생성됩니다. 이때 재귀 호출이 깊어질수록 함수 호출 스택이 커지고 함수 호출 스택이 커진다는 것은, 함수 실행 정보들이 스택에 쌓이는 것을 의미합니다. 스택은 프로그램이 순차적으로 함수를 호출했을 때 완료된 함수는 스택에서 제거하는 시스템인데, 재귀 함수의 경우 자기 자신을 계속 호출하기 때문에 각 호출마다 독립적인 함수 실행 정보를 스택에 쌓게 됩니다. 이로 인해 재귀 함수 호출을 해야하는 경우 이러한 이슈 발생 가능성에 더 유의해야 합니다.
   • 스택 오버플로우란, 스택에 더이상 새로운 함수 호출 정보를 저장할 수 없을 때 발생하며 프로그램이 비정상종료될 수 있습니다.

어떻게 개선해야 할까?

1. 중복 계산 제거

“재귀로 인한 중복 호출”을 제거하기 위해 각 계단마다 도달하기까지의 경우의 수를 배열로 저장합니다. 즉 배열의 인덱스가 각 계단의 단계를 의미합니다. 이렇게 되면 모든 n에 대한 경우의 수를 파생되는 호출 반환 값으로 연산하지 않고 이미 배열에 저장된 값에 인덱스로 접근하여 연산할 수 있습니다. 이것을 동적 프로그래밍, Dynamic Programming(DP) 기법이라고 합니다.

🤔 어디에서 DP 방식이 적용된걸까?
“큰 문제를 작은 문제를 나누어 해결하고 그 결과를 저장하여 전체 문제를 해결하는 기법”이라고 정의할 수 있으며, 여기에서 큰 문제는 n번째 계단에 도달하는 총 경우의 수를 구하는 것이고 (가장) 작은 문제는 dp[0]과 dp[1] 값라고 볼 수 있습니다.
작은 문제부터 순차적으로 구하여 그 결과들을 저장해두고 큰 문제까지 도달하는 것으로 보아, DP 접근 방식의 풀이라고 할 수 있습니다.

2. 점화식

이전 풀이 코드에서도 적용되어 있는 풀이 방식이긴 한데, 점화식은 특정 항이 이전 항들과의 관계로 표현되는 식입니다. `dp[i] = dp[i-1] + dp[i-2]` 와 같이 i에 대한 항과 i-1, i-2에 대한 항과의 관계를 식으로 표현한 것을 뜻합니다.

2차 코드

class Solution {
    func climbStairs(_ n: Int) -> Int {
        guard n > 1 else { return 1 }
        
        // index를 각 계단이라고 가정
        var dp = Array(repeating: 0, count: n+1)
        dp[0] = 1   // 0번째 계단까지의 경우의 수
        dp[1] = 1   // 1번째 계단까지의 경우의 수
        for i in 2...n {
		        // 이미 배열에 저장된 값에 인덱스로 접근하여 연산 가능!
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }
}

print(Solution().climbStairs(45))

⏱️ 시간복잡도

• 1차 코드 : 중복 호출로 인해 O(2^n)
• 2차 코드 : 순회로 인한 O(n)와 각 i에 대한 연산 O(1), 결과적으로 O(n)

📦 공간복잡도

• 1차 코드 : 재귀 호출 스택으로 인해 O(n)
• 2차 코드 : dp 배열 크기가 n+1 이기 때문에 O(n)

💨 실행속도

• 1차 코드 : 재귀 중복 호출로 인해 기하급수적으로 증가 ⇒ TLE 발생
• 2차 코드 : 0ms(leetcode 제출 기준)

회고

• 힌트에서 “스택/큐”라고 명시되어 있어 굳이 적용해야 한다면, 2차 코드에서 dp 배열을 큐로 정의하여 지난 계단에 대한 값은 pop()을 통해 제거하고 최종적으로 큐에 n번째 계단에 대한 경우의 수 값만 남아있는 구조를 예상할 수 있을 것 같다.
• 역시나 아직 피보나치 수열 풀이법을 완벽하게 이해하지 못해 문제를 보고 단번에 떠올리지 못했다. 더군다나 수학적인 피보나치 수열과 같은 프로그래밍 방식으로 DP 방식은 절대 생각하지 못했다. 이 부분에 대한 사고력을 키우기 위해서는 유사한 문제 여러개를 반복적으로 풀이해보고 접근해야봐야 단번에 접근방식을 떠올릴 수 있을 것 같다.