Python 알고리즘 문제 풀이(feat. LeetCode)

문제 70. Climbing Stairs(Easy, 49.1%)

(n층까지의 계단을 오를 때 경우의 수 구하기, 한번에 1층 또는 2층을 오를 수 있음)

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

나의 풀이

class Solution(object):
   def climbStairs(self, n):
       self.n = n
       dp = [None] *(n+1) # dp라는 n+1 크기의 리스트를 생성(초기값 선언)
       dp[0] = 1 
       dp[1] = 1 # 1층까지 오르는 방법은 1가지 이므로 1의 값 부여
       
       for i in range(2, n+1):
           dp[i] = dp[i-1] + dp[i-2] 
                               
       return dp[n]

• DP라는 개념을 공부하고 적용하였습니다.
• Dynamic Programming (동적계획법): 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용 (피보나치 수열, 계단 오르기 등 사용)
• dp[i] = dp[i-1] + dp[i-2]
  -. i번째 계단을 오르기 위해서는 i-1번째에서 올라가는 방법과 i-2번째에서 올라가는 방법 2가지
  -. 그 외에는 중복되는 방법이므로 dp[i-1] + dp[i-2]를 사용하여 dp[i]번째 방법을 구함
  -. 반복적으로 하위 문제가 상위 문제에 영향을 주는 경우 점화식을 세워 문제를 해결

DP를 공부하면서도 아직 이해가 부족한 부분이 많이 있었습니다. 점화식을 어떻게 세워야 하는지 문제를 봤을 때 바로 딱 떠오르지도 않고, 처음 보는 개념이어서 제대로 푼 게 맞는지에 대한 의구심도 들었습니다. DP가 사용되는 문제를 더 풀어보고 공부하여 온전히 제 것으로 만드는 훈련을 해야겠습니다.👍