Algorithm] 금액맞추기(일반 재귀와 메모이제이션)

일정 금액이 주어졌을때 낼 수 있는 화폐의 종류에 따른 경우의 수를 구하는 문제.

핵심은 점화식에 따라서 pay( money-BILLS[n-1]*i , n-1)을 재귀한다는 것이다.

뭐이리 재귀식이 어려운지...

%일반 재귀와 메모이제이션

일반적으로 위와 같은 코드를 사용했을때(일반 재귀) 출력물(왼쪽)과 메모이제이션을 사용했을때의 출력물(오른쪽)은 아래와 같다.

<좌. 재귀, 우.메모이제이션을 적용한 재귀>

같은 재귀 코드이지만 실행속도에서 확연한 차이를 보인다.

앞선글 http://mantdu.tistory.com/745 에서 설명한 것과 같이 메모를 이용하면 재귀에서 중복으로 함수를 CALL하는 낭비를 방지할 수 있다.

쉽게 말하면 이미 방문해서 연산한 과거의 연산물을 테이블에 저장시키고 반복적인 접근시 해당 테이블의 정보를 갖고와서 불필요한 반복수행을 방지하는 코드이다.

코드는 원본 코드와 같으나 파란색으로 표시한 네 줄을 추가하였다. 

( static int MATRIX[1000][1000]; 는 전역으로 선언하였다)

	1	2	.....	10	....	30...	80	...	100(금액)
1
2						16
3
4
5
6

예를들어 재귀의 끝에 도달해서 하나 하나 기록해나가며 table을 채운다. 만약 어느때에 (2,30)에 16이라는 비용을(경우의수) 기록하였으면 추 후 (2,30)의 경우의 수를 구할때는 따로 또 재귀를 이용하지 않고 테이블의 값을 읽어온다.