코테 스터디 27일차 TIL + 오늘의 학습 키워드 다이나믹 프로그래밍

- 오늘의 학습 키워드 다이나믹 프로그래밍

- 공부한 내용 본인의 언어로 정리하기

다이나믹 프로그래밍? 복잡한 문제를 하위 문제로 잘게 나누어서,

각  하위 문제의 결과를 저장해서 중복 계산을 피하는 방법이다.

 

수도코드 

function climbStairs(n);
	//기본 케이스
    if n<= 2;
    	return n
        
    //DP 배열 초기화
    dp[1] =1; //1개의 계단을 오르는 방법은 1가지
    
    dp[2] =2; //2개의 계단을 오르는 방법 2가지
    
    //3부터 n까지 반복
    for i from 3 to n;
    	dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]

 

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

이전에 풀었던 문제인데 구현을 못함, 하위 문제로 나눈다는것을 이해를 못했던것으로 보임

  - 어떻게 해결했는지

경우의 수가 1칸 올라갈때 2칸 올라갈때로 나뉜다.

dp[1] = 1 가지

dp[2]= 2 가지 ( 1칸+1칸 /2칸 )

n=3일때에도 dp[1]+ dp[2] 이므로 3부터 n까지 배열을 채우면 된다.

  - 무엇을 새롭게 알았는지

다이나믹 프로그래밍이 작은 단위로 나누어서 작은 단위의 결과를 저장해서

피보나치 수열 풀듯이 반복적으로 수행하면 된다.
  - 내일 학습할 것은 무엇인지