99클럽 코테 스터디 6일차 TIL + 오늘의 학습 키워드 동적 프로그래밍

- 오늘의 학습 키워드 동적 프로그래밍 (dynamic)

- 공부한 내용 본인의 언어로 정리하기(출처: leetcode)

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

문제 조건: 한번 올라갈때 1걸음 또는 2걸음 오를수 있다.

 

수도 코드

함수 climbStairs(n):
    // 기본 케이스
    만약 n = 1이면 1 반환
    만약 n = 2이면 2 반환
    
    // 각 계단에 도달하는 방법의 수를 저장할 배열 생성
    dp = 크기가 (n+1)인 새 배열
    
    // 기본 케이스 초기화
    dp[1] = 1
    dp[2] = 2
    
    // dp 배열 채우기 , 3인이유: 이미 기본 케이스에서 1,2를 초기화했기 때문이다.
    i가 3부터 n까지:
        dp[i] = dp[i-1] + dp[i-2]
    
    dp[n] 반환

 

public class ClimbingStairs {
    public int climbStairs(int n) {
        // 기본 케이스
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 각 계단에 도달하는 방법의 수를
        // 저장할 배열 생성
        int[] dp = new int[n + 1];
        
        // 기본 케이스 초기화
        dp[1] = 1;
        dp[2] = 2;
        
        // dp 배열 채우기
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

dp 배열에서 int i=3;으로 해야한다고 하는데 이해가 안갔음

  - 어떻게 해결했는지

피보나치 수열 학습했음

1칸 또는 2칸만 올라갈수 있다는 규칙

힌트

ⓐ마지막에 1칸을 올라온다

ⓑ마지막에 2칸을 올라온다

 

현재 상태는 이전 두 상태에만 의존한다.

n번째 계단에 도달하는 방법 = [n-1번째 계단에 도달하는 방법] + [n-2 번째 계단에 도달하는 방법]

기본 케이스 

1번 계단까지 오는 방법 1가지

2번 계단까지 오는 방법 2가지 

dp[1]=1

dp[2]= 2

  - 무엇을 새롭게 알았는지

피보나치 수열을 사용하는 법을 배웠음. 수학시간에 배웠던거 같은데 n번째에 도달하는 값에

피보나치 수열을 이용하는 것이 새로웠음
  - 내일 학습할 것은 무엇인지 ??

 

 

 

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