DP (Dynamic Programming)

...에러는 그냥 올려보았다.

​

다이나믹 프로그래밍.

피보나치 처럼 재귀적으로 호출되는 함수.,,

큰 문제가 작은 문제들을 포함한 경우에 대해,

내가! 한 번 푼 문제는 ! 두번 다시 풀지 않겠다!

이미 푼 결괏 값은 배열 등의 데이터에 저장해두어 읽는다.

​

​

아래는 DP (Dynamic Programming)을 적용 전이다.

pivonachi를 적용 전이다.. 대강 약 2^50의 시간 계산을 한다.

 

public static void main(String[] args) {
		long beforeTime = System.currentTimeMillis();
		DP dp = new DP(50);
		dp.getNum();
		long afterTime = System.currentTimeMillis();
		long secDiffTime = (afterTime - beforeTime);
		System.out.println("시간차이(m): " + secDiffTime);
	}

 

​

---

적용후!

​

ㅅ..ㅅㅂ

​

디버깅점..

 

dp.getNumByDP();

오오?..

​

이때 테스트할 수 있는 숫자는

Long형의 숫자의 표현 범위를 넘지 않는다.

이때의 피보나치로 표현 가능한 항의 넘버를 구해 보면...

​

피보나치 수열의 극한 값에 대한 증가율은 1.62 쯤 된다.

2^10은 천 정도, 1.62^10은 100정도 된다.

​

 

 

대략 100의 정도의 숫자에 대해 테스트해 볼 수 있다.

 

long beforeTime = System.currentTimeMillis();
		DP dp = new DP(92);
		dp.getNumByDP();
		long afterTime = System.currentTimeMillis();
		long secDiffTime = (afterTime - beforeTime);
		System.out.println("시간차이(m): " + secDiffTime);

result: 7540113804746346429
시간차이(m): 0

 

흐음.......그러하다 시간차이가 거의 발생하지 않는다.

​

아까 DP(50)에 대해서는 2^50.. 약 1천조 번 계산했고 이건 약 92번이라서 그런가 보다..

그니까 10조배 차이 나는 거지..