39. 각 동전 및 지폐로 금액 맞추기 알고리즘 (재귀 프로그래밍)

1. 개요

금액 맞추기 알고리즘은 쉬움.

재귀 알고리즘 문제로 단골 손님.

앞선 이항계수와 마찬가지로 대표적인 재귀 알고리즘 중 하나.

알고리즘의 원리

6가지 지폐로 금액 m을 맞추는 방법은

금액 m을 5가지 지폐로 맞추는 방법

+

금액 m - (6번째 지폐 * i)을 5가지 지폐로 맞추는 방법

(i란 6번째 지폐의 개수로 위의 식의 결과가 0보다 클 때까지 재귀 방법을 구한다.)

2. 문제

주어진 지폐들로 금액 m을 맞출 수 있는 경우의 수를 구하시오.

(반복, 일반적 재귀, 그리고 재귀적 방법에 대한 수행시간 효율을 증가시키는 방법 3가지 구현하시오.)

3. 코드

3-1) 반복

3-2) 일반적 재귀

3-3) 속도 증가 재귀

3-4) 출력

4. 정리

마지막 속도 향상 재귀 알고리즘은 메모이제이션을 활용하지 않고도 어마어마한 속도의 증대를 이루어내었다.

이 방법으로 인해 내가 가진 생각의 한계가 조금은 풀린 느낌이다.

계속해서 이미 알고있는 방식이라 할 지라도 더 개선할 수 있는 방법들을 찾고 생각하자.

t = money / bills[n-1] 

부분은

현재의 돈을 현재 검사하는 지폐의 가치로 나누었을 때(money / bills[n-1])의 의미는

결국 현재 지폐를 사용할 수 있는 최대의 수(t)다.

그리고 진짜 이 코드에서 2번째 코드와 3번째 코드를 비교했을 때

획기적으로 속도가 줄여지는 부분은

재귀 함수의 끝을 결정하는 맨 처음 부분이다.

종료 조건에 따라 재귀의 깊이를 획기적으로 줄여낼 수 있다.

출력 부분을 보면 두 코드의 속도의 차이가 어마어마하게 난다는 것을 알 수 있다.

*기억해야할 점: 재귀의 종료 조건의 설정에 따라 

지수적 시간이 걸릴 수 있고, 로그적 시간이 걸릴 수 있다는 것을 반드시 기억하자!!!

결국 메모이제이션도 재귀 호출을 줄이는 방법 중의 하나일 뿐이다.

대표적인 방법이 메모이제이션이지만 메모이제이션 방법뿐 아니라 재귀 호출의 반복을 막는 방법이 

있다는 것을 염두해두고 계속 찾아보자. 최선의 방법을.