[LeetCode] 509. Fibonacci Number (JAVA)

leetcode.com/problems/fibonacci-number/

Fibonacci Number - LeetCode

일반적인 재귀함수 풀이 (= 내 풀이)

 public int fib(int n) {
      int result = 0;

      //1. if문으로 했을 때
      if(n==0){
        result=0;
      }else if(n==1){
        result=1;
      }else{
        result=fib(n-1)+fib(n-2);
      }

      //2. switch문
      switch(n){
        case 0: result=0; break;
        case 1: result=1; break;
        default: result=fib(n-1)+fib(n-2);
      }

      return result;
    }

➡ if문을 사용하나 switch문을 사용하나 재귀함수를 썼을때는 런타임이나 메모리는 별 차이가 없다.

➡ 런타임 12 ms, 메모리 35.7 MB

➡ 재귀함수는 방식이 더 간단하지만, n이 증가함에따라 호출되는 함수의 수가 기하급수적으로 증가함

➡ 일정 수 이상의 순열을 구하기 어려움 & 프로그램이 기존에 했던 계산 작업을 또 해야함

 

 

Memoization 방식으로 풀이

    public int fib(int n) {
      int [] arr = new int [n+1];

      arr[0] = 0;
      arr[1] = 1;

      if(n<2){
          return arr[n];
      }

      for(int i=2;i<n+1;i++){
          arr[i] = arr[i-2] + arr[i-1];
      }

      return arr[n];
    }

[ 동적프로그래밍 ] 에서는

- 작은 문제가 반복

- 같은 문제는 구할때마다 정답이 같다

➡ 한 번 계산한 작은 문제를 저장해놓고 다시 사용한다 : Memoization 

➡ 0번째, 1번째 수열은 항상 값이 같으므로 배열에 미리 저장

➡ 2번째 수열을 구할때에는 배열에 저장된 값을 이용 ... 이 방식으로 n 번째 수열 구하기

➡ 런타임 0 ms, 메모리 35.8 MB

 

잘 해놓고,, 바보처럼 배열선언할때 30으로 했음

0~30 이니까 31개가 필요한데..; 인덱스 꼭 주의하자..

 

Bottom-Up 방식으로 풀이

작은 문제부터 차근차근 구현하는 방법

    public static int fib_Bottom_Up(int n) {
    	if(n<=1) {
    		return n;
    	}
    	
    	int first = 0;
    	int second = 1;
    	
    	int next = 0;
    	for(int i=0;i<n-1;i++) {
    		next = first + second;
    		first = second;
    		second = next;
    	}
    	return next;
    }

➡ n-1 까지만 for문을 돌리는 이유 : 마지막 번째에는 first 와 second를 바꿀 필요가 없어서 (?)

 

Top-Down 방식으로 풀이

재귀함수로 구현하는 부분.

큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그제서 작은 문제를 해결함.

public static int fib_Top_Down(int n) {
  int [] arr = new int [n+1];
  if(arr[n]>0) {
  	return arr[n];
  }

  if(n<=1) {
  	return n;
  }else {
  	arr[n] = fib_Top_Down(n-1) + fib_Top_Down(n-2);
 	return arr[n];
  }
}

➡ 맨 위에 if는 왜 하는걸까..?

 

 

[ 생각 할 거리 ]

• 왜 n은 30까지로 해놨을까?
• 30이 넘으면 어떻게 되는지 돌려보기 (결과값이 음수가 나옴..)
• overflow => n이 30, 50, 100, 500일때 구해보기 (30 정상 50 음수 100 음수 500 정상)

n=47 부터 음수값으로 넘어감
arr[45] = 1134903170
arr[46] = 1836311903
arr[47] = -1323752223
➡ int 자료형의 범위를 벗어나서 => Overflow 발생
➡ int range -2,147,483,648 to 2,147,483,647

➡ 정수 오버플로우(Integer Overflow) : 정수형의 크기는 고정되어있음 (range) 해당 자료형이 저장할 수 있는 값의 크기보다 큰 값을 저장하려고 할때 실제 저장되는 값은 의도하지 않게 아주 작은 수이거나 음수가 되는 보안 취약점

➡ 표준에 맞춰진 컴파일러가 오버플로우를 무시하여 프로그램의 에러를 방지하지 못함 (잘못된 값이 저장됨)

 

 

Dynamic Programming (동적계획법)
galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

➡ 큰 문제를 작은 문제들로 분할하여 그것을 이용해 큰 문제를 해결하는 방식

➡ 분할정복과 다른점 : DP의 경우 작은 부분 문제의 답이 항상 같아야 함

 

 

참고 :

galid1.tistory.com/507
m.blog.naver.com/wwwkasa/80180210172