피보나치수열(재귀,메모이제이션)
문제
N항 까지의 피보나치 수열을 출력하기.
나의 풀이
class Main2 {
public int DFS(int n) {
if(n==1) return 1;
else if(n==2) return 1;
else return DFS(n-2) + DFS(n-1);
}
public static void main(String[] args) {
Main2 T = new Main2();
int n = 10;
for(int i=1;i<=n;i++) System.out.println(T.DFS(i));
}
}
++ 메모이제이션 사용(시간단축)
class Main2 {
static int[] fibo;
public int DFS(int n) {
//이미 fibo배열에 값이 존재한다면, 탐색하지않고
if(fibo[n]>0) return fibo[n];
if(n==1) return fibo[1] = 1;
else if(n==2) return fibo[2] = 1;
else return fibo[n] = DFS(n-2) + DFS(n-1);
}
public static void main(String[] args) {
Main2 T = new Main2();
int n = 45;
fibo = new int[n+1];
T.DFS(n);
for(int i=1;i<=n;i++) System.out.println(fibo[i]);
}
}
풀이방법
첫번째 풀이는 재귀를 통해 단순히 값을 출력하는 방법이다.
하지만, 이렇게 단순히 재귀만을 하게되면 N값이 커졌을때, 모든 tree를 탐색해야하므로 시간이 오래걸린다.
예를들어, DFS(45)는 DFS(43) + DFS(44)인데 그값을 도달하기위해
또, DFS(44) = DFS(42) + DFS(43) .... 이런 과정을 쭉~ 거쳐야하므로,
비효율적이다.
DFS(N)값이 생성될때 fibo배열에 그 값을 저장하고 가져다쓰는 메모이제이션을 이용하면 시간단축을 획기적으로 할 수있다.
하지만, 재귀함수를 이용한 방법을 절대적으로 배열을 이용해 출력하는방법보다 느릴수밖에 없다.
왜냐하면, 재귀함수는 한번 재귀될 때마다 stack frame에 매개변수,지역변수,주소 등이 쌓이고 이는 배열보다는 비효율적이기 때문이다.
핵심키워드
재귀함수가 비효율적인 순간이 많기는해도, 어떻게 쓰는지, 어떻게 값이 쌓이는지 이해하자!
Author And Source
이 문제에 관하여(피보나치수열(재귀,메모이제이션)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zmdals/피보나치수열재귀메모이제이션저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)