[동적 프로그래밍/JAVA] 메모이제이션 파헤치기

항상 동적 프로그래밍 앞에만 서면..

작아지는 나..

이제는 그러지 않겠다는 마인드를 가지고!!

대대적인 DP 정복 포스팅을 시작해보자~

첫 번째 주제는 메모이제이션 기법이다!

그렇다면 완벽한 DP를 위해 달려보자.

---

동적 계획법은 무엇일까?

-> 복잡한 문제를 간단한 여러 가지 문제로 나누어서 푸는 방법. 

-> 중복된 부분을 제외하여 한번만 계산하고도 구할 수 있어서 시간, 공간 복잡도를 줄일 수 있는 장점이 있다.

 

피보나치를 구하는 두가지 방법

1. 재귀를 이용하여 그냥 구하기.

-> 답은 나오지만 숫자가 커질수록 되풀이되는 함수가 많아져서 시간이 오래 걸린다. (시간 복잡도 : O(2^n))

static long fibo(int N) {
		if (N <= 1) {
			return N;
		} else {
			return fibo(N - 1) + fibo(N - 2);
		}
	}

 

2. 메모이제이션을 이용하여 구하기.

-> 한번 구한 계산은 더 이상 계산하지 않고 가져다 쓰는 개념이라 시간이 확 줄어든다. (시간 복잡도 : O(n))

	static long[] arr = new long[51];	// 저장해둘 배열 선언

	static long fiboMemoization(int N) {
		if (N == 0) {
			return arr[0];
		} else if (N == 1) {
			return arr[1];
		} else if (arr[N] != 0) {	// 한 번 이상 구한 것은 바로 저장된 값 리턴!!
			return arr[N];
		} else {
			return arr[N] = fiboMemoization(N - 1) + fiboMemoization(N - 2);
		}
	}

 

 

두개 기법 비교!

1. 재귀를 이용하여 그냥 구하기.
답 : 1134903170
실행 시간 : 3.994
-------------------------------------
2. 메모이제이션을 이용하여 구하기.
답 : 1134903170
실행 시간 : 0.0

-> 45의 피보나치수열을 구했을 때 위와 같이 나타난다. 숫자가 커지면 커질수록 실행시간의 차이는 커지게 된다.

 

결론

-> 메모이제이션을 잘 사용하자! 동적 계획법을 효율적으로 짤 수 있다!