99클럽 코테 스터디 8일차 TIL + 리트코드 70번 Climbing Stairs(Python)

✔️오늘의 학습 키워드

• 다이나믹 프로그래밍
• leetcode 70번 Climbing Stairs

✔️ 공부한 내용

📌 오늘의 문제

📌 작성 코드

class Solution:
    def climbStairs(self, n: int) -> int:
        step = [0] * (n + 1)
        step[1] = 1
        if n >= 2:
            step[2] = 2
        for i in range(3, n+1):
            step[i] = step[i-2] + step[i-1]
        return step[n]

✔️ 오늘의 회고

📌 문제 및 시도 방법

동적계획법을 사용하여 문제를 풀었다.

📌 문제 해결 방법

1. 계단 오르는 수를 저장하는 리스트(step) 생성
2. n= 1일 경우 1로 저장, n이 2보다 크면 2번째에 2로 저장
3. 3번째부터는 i-2, i-1에 저장된 값을 더해가며 step 리스트에 저장
4. 이제 계단 오르는 방법의 수가 저장된 리스트에서 우리가 필요한 step[n] 값을 리턴

📌 새롭게 안 내용

class Solution:
    def climbStairs(self, n: int) -> int:
    	if n <= 2:
        	return n
        a, b = 1, 2 
        for _ in range(3, n + 1):
        	a, b = b, a + b
        return b

이렇게 훨씬 간단하고 깔끔하게 풀 수 있는 방법이 있어 가져왔다.

📌 내일 학습할 내용

내일의 알고리즘 문제를 풀어보고 이해하기

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL