f[n] = f[n-1] + f[n-2]
위의 식을 계산하는 가장 빠른 방법은?
1. Fibonacci Numbers
: f[n] 부터 시작해서 f[1]을 끝으로 2의 n승 회의 연산이 필요, 너무 많은 연산이 반복됨. 단순분할정복이라고도함.
int finbonacci (int n) {
int[] f = new int[100];
/*
if(n==1 || n==2) {
return 1;
} else {
return finbonacci(n-2) + finbonacci(n-1);
}
*/
if(n == 1) return 1;
if(n == 2) return 1;
return f[n] = finbonacci(n - 1) + finbonacci(n - 2);
}
2. Memoization
: 이미 계산된 f값(중간 계산결과)을 캐싱함으로써 중복계산을 피하는 방법. n회의 연산만 필요하게 됨.
int memoization(int n) {
int[] f = new int[100];
/*
if(n==1 || n==2) {
return 1;
} else if(f[n] > -1) { // f[n]을 -1로 초기화 했다는 가정, 즉 f[n] > -1은 이미 계산된 값
return f[n] ; // 이미 계산된 값을 재사용
} else { // 새로 계산한 값을 캐시에 저장
f[n] = finbonacci(n-2) + finbonacci(n-1);
return f[n];
}
*/
if(n == 1) return 1;
if(n == 2) return 1;
if(f[n] != 0) return f[n];
return f[n] = memoization(n - 1) + memoization(n - 2);
}
3. Buttom-Up
구하려는 f[n]에서 시작하는 recursion이 아니라, 1부터 시작해서 순서대로 계산한다. 따라서 f[n]을 계산하려는 시점에 이미 f[n-1]과 f[n-2]가 계산되어 있으므로 중복계산이 없음. 순환식에서 일반적, 상식적으로 사용.
f[1] = 1; f[2] = 1;
for(int i = 3; i <=n; i++) {
f[i]=f[i-1]+f[i-2];
return f[i];
}
4. 1, 2성능비교
public static void main(String[] args) {
FibonacciNumbers fn = new FibonacciNumbers();
long startF = System.currentTimeMillis();
System.out.println(fn.finbonacci(30));
long endF = System.currentTimeMillis();
long startM = System.currentTimeMillis();
System.out.println(fn.memoization(30));
long endM = System.currentTimeMillis();
System.out.println("피보나치 실행시간 : " + (endF - startF)); // 206
System.out.println("DP 실행시간 : " + (endM - startM )); // 128
}
30번째 수를 구할 시 단순분할 206 vs DP 128
참고한 자료. 아주 좋은 설명.
www.youtube.com/watch?v=K15qLnKKrow&t=499s
www.youtube.com/watch?v=FmXZG7D8nS4
'Algorithms & CS' 카테고리의 다른 글
[Python] 프로그래머스 - 완주하지 못한 선수 (0) | 2021.08.10 |
---|---|
[Python] 프로그래머스 - 가장 큰 수 (0) | 2021.08.09 |
[Javascript] 프로그래머스 - 위장 (0) | 2020.08.29 |
자바 메모리 구조 이해하기 - Stack, Heap (0) | 2019.07.30 |
[Java] 프로그래머스 - 같은 숫자는 싫어 (0) | 2019.07.18 |