백준 BOJ 1003번

---

접근 방법

 

겉보기에는 매우 단순해보인다.

그냥 피보나치 함수에서 0, 1이 출력될 때 카운트만 해주면 될 것 같지만, 시간 초과로 오답이다.

이 문제는 Dynamic Programming 줄여서 DP를 사용해야 한다. (다른 블로그를 보니 재귀함수로 푸는 방법도 있더라)

 

일단 이번에는 DP에 대해서 알아보자.

 

 

Dynamic Programming (DP)

 

DP는 기본적으로 주어진 큰 문제를 작은 문제로 나누어서 풀되, 반복되는 연산을 줄이는 방법이다.

 

DP의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. DP를 사용하는 알고리즘도 주어진 문제를 작게 나누어 각 작은 문제의 답을 계산하고, 이를 이용해 본 문제의 답을 계산하기 때문이다.

 분할정복과 차이는 반복되는 문제를 한 번만 푼다는 점이다. DP의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 이용함으로써 속도를 향상시킨다.

 

이렇게 이미 풀린 작은 문제를 다시 풀지 않고 재활용하는 것을 메모이제이션(Memoization) 이라고 한다.

 

문제로 나온 김에 피보나치를 예를 들면, 재귀를 이용한 피보나치는 다음과 같다.

int fib(int n) {
	if(n == 0) return 0;
	if(n == 1) return 1;
 
	return fib(n - 1) + fib(n - 2);
}

만약에 fib(5)을 구하려면,

1. fib(5)
2. fibi(4) + fibi(3)
3. ( fib(3) + fib(2) ) + ( fibi(2) + fib(1) )
4. ( ( fib(2) + fib(1) ) + ( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) )  + fib(1) )
5. ( ( ( fib(1) + fib(0) ) + fib(1) ) + ( fib(1) + fib(0) ) ) + ( ( fib(1) + fib(0) ) + fib(1) )

쓰기 힘들다.

fib(5) 를 구하는데만 해도 fib(2)를 중복해서 연산한다. 이 때문에 재귀함수를 호출하기 때문에 시간이 매우 낭비된다.

 

 

 

다음은 DP 방식이다. 배열을 만들어서 fib의 결과값을 저장해놓고 재활용한다.

static int[] store = new int[];
 
store[0] = 0;
store[1] = 1;
 
int fib(int n) {
	if(store[n] == -1) {
		store[n] = fib( - 1) + fib(n - 2);
 	}
	return store[n];
}

이렇게 되면, 중복된 값을 호출할 경우 다시 재귀함수를 호출하는 것이 아니라, 배열에 저장되어 있는 값을 사용하기 때문에 n이 크면 클수록 시간적으로 이득을 볼 수 있다. 

---

코드

import java.util.*;

public class Main {
   static Integer[][] dp = new Integer[41][2];
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      dp[0][0] = 1;
      dp[0][1] = 0;
      dp[1][0] = 0;
      dp[1][1] = 1;
      int n = in.nextInt();
      for(int i = 0; i < n; i++){
         int temp = in.nextInt();
         fibonacci(temp);
         System.out.println(dp[temp][0]+" "+dp[temp][1]);
      }
      in.close();
   }
   static Integer[] fibonacci(int n){
      if (dp[n][0] == null || dp[n][1] == null) {
         dp[n][0] = fibonacci(n-1)[0] + fibonacci(n-2)[0];
         dp[n][1] = fibonacci(n-1)[1] + fibonacci(n-2)[1];  
      }
      return dp[n];
   }
}