동적 계획법, DP, 피보나치 수열, 이항계수 (컴공선배 강의)

동적계획법이라는 이름은 전혀 연관성이 없으므로 생각하지 않는게 좋다

 

n = 10일때를 구하기 위해 n =9,8,7,6 일때를 먼저 구해서 더 큰 경우를 구하는 것

 

둘다 DP 테이블에 작은 문제의 답을 담아두는것은 동일함

 

 

메모이제이션을 이해할 수 있느 간단한 예시

 

 

DP에서 자주 나오는 수열 개념 (구현하는데 반복문, 재귀 둘 다 사용가능하다) 

 

둘 중 재귀를 생각해보자

f(6)을 구하기 위해 하나하나 따져보면 f(4), f(3)과 같이 반복적으로 값이 사용되는 것을 볼 수 있다

이런 경우 작은 부분의 값을 미리 구해서 어딘가에 저장해두면 다음부터는 쓸모없는 연산을 줄일 수 있다

이렇게 답을 저장해두는 것을 캐싱이라고 하며 성능에서 엄청난 차이를 보인다

 

차이점

bottom-up(반복문) 방식은 다음 단계를 위해 이전 단계가 필요하기 때문에 절차대로 이어갈 수 있도록 해야하고

top-down(재귀) 방식은 원하는 단계를 원하는 시점에 바로 호출할 수 있기 때문에 절차에 대해 고려할 필요가 없다

 

따라서 구현은 top-down이 더 쉬운편이다 

 

 

이항계수

 

맨 아래 공식은 삼각수를 통해 이해할 수 있다

이항계수도 마찬가지로 반복되는 지점이 많기 때문에 메모이제이션이 필요해보인다

 

DP 비교

점화식 찾는것이 가장 중요하고 관건이다!

 

 

자료,강의

https://www.udemy.com/course/comgong_codingtest/