재귀를 적용한 동적계획법 문제를 풀기 전에 필독!

재귀.. 너무 헷갈리고 어렵다. 

그래서 재귀가 더이상 어렵지 느껴지지 않도록 정리를 한 번 해보았다.

재귀함수를 쓰면서 dp를 적용하는 것이 왜 효율적인지 분석해보았으며 재귀를 적용한 dp를 어떤식으로 구현하면 좋을지 고민해 보았다.

먼저 기본적인 예시를 들어 난이도를 올려가며 문제 풀이를 하였다.

 

일반적인 재귀함수.

 

재귀함수는 이 두가지가 중요하다.

1. 재귀를 적용시킬 점화식 세우기.

2. 종료조건

 

재귀 함수에는 여러가지가 있지만 대표적으로 피보나치 함수를 재귀 함수로 구현할 수 있다.

피보나치 함수의 점화식은 다음과 같다.

F(n)=F(n-1)+F(n-2) 

따라서 F(n-1)+F(n-2)을 재귀함수를 통해 반복을 하면 되고 종료조건은 n=1 또는 n=2일때 1를 리턴시켜 종료시켜주면 된다. 

소스코드를 살펴보자

 

 

입력값으로 7을 주고 위 프로그램을 실행시키면 

다음과 같이 출력이 된다. 

이 출력과정을 그림으로 그려보면

이렇게 7이나 6,5에서 그 하위부분인 f(1), f(2), f(3), f(4)를 구했음에도 불구하고 매번 f(4)를 구하기위해 다시 f(1), f(2), f(3)을 호출을 해야한다.  f(7)을 구하기 위해서 총 f(1)이 5번, f(2)가 8번 씩이나 호출이 된다.

 

이렇게 함수 호출의 중복을 막기 위해 메모이제이션을 하게된다.

위의 피보나치 함수를 예로들면 f(1),f(2)등 하위 함수의 중복 호출을 방지하기 위해 해당 함수값을 메모를 하여 기억하여 활용하는 방식이다.

 

전역변수로 memo[(n사이즈)]만큼 할당을 한다.

그리고 피보나치 함수 내에 메모이제이션을 적용한 종료조건을 추가시켜주면 된다.

 

기존에 있던 종료조건인 

if (n == 1 || n == 2)return 1;

은 그대로 넣고

if(memo[n]>0)return memo[n]을 추가시키면 되는데 이 코드의 의미를 해석하기 위해 먼저 위의 트리구조를 다시 한 번 보자. 호출됐던 함수는 결국 왼쪽 최하위노드까지 내려가다가 다시 상향식으로 올라가게 되는데 그러면서 제일 먼저 1,2가 리턴이 되고 그다음으로 낮은 f(3)=f(1)+f(2)즉 memo[3]=2로 제일 먼저 저장이 된다. 이렇게 f(3)값이 저장이 돼 있기때문에 다음에 f(4)=f(3)+f(2)을 구하기 위해서  f(1)과 f(2),f(3)를 호출할 필요가 없어진다. 이런식으로 f(4), f(5)가 memo배열에 차례차례 저장이 되면서 불필요한 함수의 중복호출을 효과적으로 줄일 수 있다.

 

소스코드를 보면

 

이고 출력화면은 다음과 같다.

이렇게 f(3)부터f(5) 순차적으로 저장이 되면서 불필요한 함수 호출이 사라지게 된다.

 

정말 기초적인 문제였지만 다른 재귀를 적용해야하는 동적계획법 문제들도 점화식을 알고, 종료조건(기존 종료조건 + 추가메모이제이션 조건)을 걸어줘야 하는 핵심은 동일하다.