반응형
공지사항
-
재귀를 적용한 동적계획법 문제를 풀기 전에 필독!공지사항 2019. 12. 29. 21:24
재귀.. 너무 헷갈리고 어렵다. 그래서 재귀가 더이상 어렵지 느껴지지 않도록 정리를 한 번 해보았다. 재귀함수를 쓰면서 dp를 적용하는 것이 왜 효율적인지 분석해보았으며 재귀를 적용한 dp를 어떤식으로 구현하면 좋을지 고민해 보았다. 먼저 기본적인 예시를 들어 난이도를 올려가며 문제 풀이를 하였다. 일반적인 재귀함수. 재귀함수는 이 두가지가 중요하다. 1. 재귀를 적용시킬 점화식 세우기. 2. 종료조건 재귀 함수에는 여러가지가 있지만 대표적으로 피보나치 함수를 재귀 함수로 구현할 수 있다. 피보나치 함수의 점화식은 다음과 같다. F(n)=F(n-1)+F(n-2) 따라서 F(n-1)+F(n-2)을 재귀함수를 통해 반복을 하면 되고 종료조건은 n=1 또는 n=2일때 1를 리턴시켜 종료시켜주면 된다. 소스코드..