궁극적인 목표는 memoization을 기록하기 위한 글이다.
피보나치 수열 문제를 for, 배열, 재귀를 통해 풀어보고자 한다.
물론 for 문이나 배열 말고 재귀를 통해 풀게 되면 성능이 안 좋다. 이유는 스택 프레임이 돌아가기 때문이다. 근데 알아둬서 나쁠 거 없으니까..
물론 재귀를 통한 방법도 메모이제이션을 활용하면 성능 개선은 가능하다.
피보나치는 정말 기본적인 문제이지만 기본적인 것을 튼튼히 기록해두자. 알아둬서 나쁠 거 없음.
피보나치 수열이란?
앞의 두 개 항을 더해서 다음 항이 생기는 것이다.
첫 번째, 두 번째 1은 무조건 있다. 즉 1 1 2 3 5 8 이런 식
문제
피보나치 수열을 출력한다.
입력 : 첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
출력 : 첫 줄에 피보나치 수열을 출력한다.
배열을 이용한 피보나치 수열
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] answer = new int[n];
answer[0] = 1; // 첫 번째 1
answer[1] = 1; // 두 번째 1
for(int i=2; i<n; i++) answer[i] = answer[i-2] + answer[i-1]; // 세 번째 수 부터 배열에 수열 넣기
for(int x : answer) System.out.print(x + " "); // 정답 출력
}
}배열을 이용한 피보나치 수열이다. 앞의 두 개의 항을 더해서 다음 항을 구한다. 하지만 누군가 배열 쓰지말고 하라고 한다면 아래와 같이 할 수도 있다.
그럼 for 문을 이용해서 작성해보자
for 문을 이용한 피보나치 수열
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a=1, b=1, c;
System.out.print(a+ " " + b+" "); // 첫 번째 두 번째 출력.
// for 문 이용 피보나치 수열
for (int i = 2; i <n ; i++) {
c = a + b;
System.out.print(c + " ");
a=b;
b=c;
}
}
}위와 같이 간단히 작성할 수도 있다. 위 코드는 밀어내기를 하는 느낌
그런데 이것도 하지 말고 재귀로 작성해보라고 한다면 아래와 같이 하면 된다.
피보나치 재귀
어렵지 않으니 코드부터 보자면
public class Main {
static int[] fibo; // 피보나치 수열 배열
public int DFS(int n ){
if(n==1) return fibo[n]=1; // 첫 번째
else if(n==2) return fibo[n]=1; // 두 번째
else return fibo[n]=DFS(n-2) + DFS(n-1);
}
public static void main(String[] args) throws IOException {
Main T = new Main();
int n = 10; // n 은 10으로 지정
fibo = new int[n+1];
T.DFS(n);
for(int i = 1; i<=n; i++) System.out.print(fibo[i] + " "); // 출력
}
}이런 식으로 구현이 가능하다. n 값은 10으로 지정했다.
출력할 때 for 문에서 매번 DFS를 호출해도 되지만 그건 성능이 너무 안 좋다. 그래서 DFS(10)만 호출해도 되도록 배열(fibo)에 기록해두는 방법을 썼다.
하지만 위의 코드보다 더 좋은 성능으로 구현이 가능하다.
이 글의 원래 목적인 메모이제이션을 활용하는 것이다.
피보나치 수열(메모이제이션)
사실 코드 한 줄만 더 추가하면 된다.
public int DFS(int n ){
if(fibo[n]>0) return fibo[n];
// 이미 구해둔 값이 있다면 바로 return
if(n==1) return fibo[n]=1; // 첫 번째
else if(n==2) return fibo[n]=1; // 두 번째
else return fibo[n]=DFS(n-2) + DFS(n-1);
}메모이제이션을 활용하여 시간 복잡도를 확 줄인 경우이다.
아래 코드 한 줄만 더 추가한 것이다.
if(fibo[n]>0) return fibo[n]; 
fibo 배열에 이미 구해둔 값이 있다면 바로 그 값을 return 하면 된다.
그 방법은 우선 배열은 동적으로 잡으면 0으로 초기화 된다.
그래서 0 보다 큰지 알아보고, 크다면 값이 이미 존재한다는 것이다.
그래서 그 값을 바로 return 하면 된다.
정리
다양한 방법으로 피보나치 수열을 구현해봤다. 또 메모이제이션을 활용하여 조금 더 좋은 성능을 구현해보았다. 그런데 중요한 것은 우선 재귀는 함수 호출될 때 마다 프레임이 생성된다. 그래서 성능이 for 문으로 하는 것 보다 안 좋다! 아무튼 잘 알아두어야겠다.
끝 !
