40. 순서를 생각하지 않는 수분할 알고리즘 (재귀 프로그래밍)

1. 개요

수분할 알고리즘은 쉬움.

재귀 프로그래밍의 대표적인 예.

n 수분할은 자연수 n을 순서에 상관 없이 하나 이상의 자연수의 합으로 나타내는 방법.

(예를들어) 

3의 수분할은 1+1+1, 2+1, 3 이렇게 3가지 방식이 존재.

이곳에서 살펴볼 수분할은 n/m 수분할이다.

n/m 수분할은 자연수 n을 m이하의 자연수만으로 수분할 하는 방법.

(예를들어) 

(3,2) 수분할은 2가지 경우 존재, 1+1+1, 2+1 

(3,1) 수분할은 1가지 경우 존재, 1+1+1 

만약 맨 위의 경우를 얻고 싶다면 인자를 n/n을 넣으면 된다.

수분할 점화식

점화식은 2가지 방식 존재.

(1) partition(n,m) = partition(n-1,1)+partition(n-2,2)+...+partition(n-m,m)

(2) partition(n,m) = partition(n-m,m) + partition(n,m-1)

2가지 점화식을 코딩.

2. 문제

n과 m을 입력하면 그에따른 수분할 경우의 수를 구하는 알고리즘을 작성하시오.

(일반적인 재귀, 메모이제이션 방법 2가지 모두 구현하고 비교하시오)

3. 코드

3-1) 일반적 재귀 방법

3-2) 메모이제이션 방법

3-3) 출력(5,3)

3-4) 출력(50,20)

3-5) 코드 3 (코드 2의 개선)

3-6) 출력(200,70)

4. 정리

결과를 보면 코드 1번, 2번, 3번 모두 어마어마한 속도의 개선이 일어났다.

특히, 코드 2번과 3번은 오직 단 한 줄의 코드만 살짝 바뀌었다.

if(n==0) return 1; >>> if(n==0) return MEMO[n][m] = 1; 으로 바뀌었는데 속도는 어마어마하게 차이난다.

그 이유는 끝처리 부분에서 메모이제이션을 활용 할 수 있는 부분을 놓친 결과 이런 차이를 만든다.

메모이제이션 역시 꼼꼼하게 처리해야하는 것!! 을 잊지말고

또한 할 수 있는 모든 부분에 메모이제이션을 처리하자. 

이번 재귀 프로그래밍을 공부하면서 배운 것.

알고리즘 공부란 단순히 외우고 점화식을 아는 수준에서 그치는게 아니라

코드의 속살을 정확히 파악하고 어떻게 가공할 수 있는지, 어떻게하면 효율적으로 바꿀 수 있는지

정말 깊은 원리까지 알고 적용할 수 있는 것이 알고리즘 공부이다.

그러니까 빨리 빨리 많이 공부한다해서 좋은게 아니야.

간단한 문제라도 정말 정확히, 그 문제를 이리저리 고치고 돌리고 뜯어보는 과정속에서

그 문제를 정확히 이해하게 되는 것이란걸

잊지말자.