백준 1003. 피보나치 함수(JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static Integer[][] dp = new Integer[41][2];

	public static void main(String[] arge) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int test_case = Integer.parseInt(br.readLine());
		
		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
		
		for(int i = 0 ; i < test_case; i++) {
			int num = Integer.parseInt(br.readLine());
			fibonachi(num);
			System.out.println(dp[num][0] + " " + dp[num][1]);
		}
		System.out.println(" ");
	}
	
	static Integer[] fibonachi(int num) {
		if(dp[num][0] == null || dp[num][1] == null) {
			dp[num][0] = fibonachi(num - 1)[0] + fibonachi(num - 2)[0];
			dp[num][1] = fibonachi(num - 1)[1] + fibonachi(num - 2)[1];
		}
		return dp[num];
	}
}

○ 문제 요약

피보나치 수열을 구하는 메소드를 fibonachi(int num)라고 했을 때 fibonachi(1)과 fibonachi(0)이 몇 번 호출되는지 출력해라.

○ 문제 풀이

익숙한 문제였기 때문에 단순 재귀 함수로 0과 1이 호출될 때마다 증가 연산자로 횟수를 올리고 출력했더니 시간 초과라는 결과가 나왔다. 시간 초과라는 결과를 보자마자 갑자기 정신이 확 들었다. 이 문제의 알고리즘 분류를 보면 다이나믹 프로그래밍 즉, 동적 계획법이라고 쓰여있는 것이다. 처음 접하는 단어이기 때문에 알아가는 시간이 필요했다. 

동적 계획법은 큰 문제를 해결할 때 작은 문제로 나눠서 해결한 뒤 결과를 저장하고 큰 문제를 해결할 때 사용한다.

정의한 것을 보면 '뭐지?'라는 반응이 나올 수 있다고 본다. 하지만 지금부터 설명을 보면 충분히 이해할 수 있다.

먼저 이전까지 피보나치 수열을 구하는 방법은 재귀 함수를 써서 매번 같은 수가 호출될 때마다 해당 연산을 했다.

하지만 그만큼 시간을 많이 쓰기 때문에 비효율적이다. 그래서 시간을 효율적으로 쓰기 위해 이전에 연산한 결과를 저장하여 호출되면 저장한 값을 재사용하기로 한다.

 

dp라는 이름의 배열을 Integer 타입으로 선언한 것은 null 체크를 하기 위해 int타입이 아닌 Integer 타입을 선언했다.

dp[0][0] = 1; >> num이 0일 때 0 호출 횟수.
dp[0][1] = 0; >> num이 0일 때 1 호출 횟수.
dp[1][0] = 0; >> num이 1일 때 0 호출 횟수.
dp[1][1] = 1; >> num이 1일 때 1 호출 횟수.

피보나치 수열을 구할 때 0을 호출하면 0을 리턴하고 1을 호출하면 1을 리턴하라고 초기화하는 것이랑 같다.

num = 0

if(dp[0][0] == null || dp[0][1] == null){ >> 미리 초기화를 해놨기 때문에 조건을 충족하지 않는다.

}

return dp[0]; 

 

dp[0]을 리턴하면서 fibonachi(0)을 탈출 -> System.out.println(dp[0][0] + " " + dp[0][1]) -> 0 1 출력

---

1은 0과 실행 과정이 같기 때문에 생략하고 3을 입력받았을 때 실행 과정을 설명하겠다.

num = 3

if(dp[3][0] == null || dp[3][1] == null){ >> 조건에 충족해서 if문을 실행한다.

 dp[3][0] = fibonachi(2)[0] + fibonachi(1)[0];  >> fibonachi(2) 와 fibonachi(1)을 실행한다. 

 dp[3][1] = fibonachi(2)[1] + fibonachi(1)[1];

}

return dp[3];

 

fibonachi(2) 

if(dp[2][0] == null || dp[2][1] == null){ >> 조건 충족

 dp[2][0] = fibonachi(1)[0] + fibonachi(0)[0] ; 

 -> fibonachit(1)과 fibonachi(0)은 null이 아니기 때문에 각각 dp[1]과 dp[0]을 반환한다.

     dp[2][0] = dp[1][0] + dp[0][0]  >> ( 0 + 1)

  dp[2][1] = fibonachi(1)[1] + fibonachi(0)[0] ; 

 -> 위와 마찬가지로 dp[1]과 dp[0]을 반환한다.

     dp[2][1] = dp[1][1] + dp[0][1] >> ( 1 + 0)

}

return dp[2];

---

fibonachi(1) 

if(dp[1][0] == null || dp[1][1] == null){ >> 조건 불충족

}

return dp[1];

---

이제 반환받은 배열 값을 이용해서 값을 구해보자. 

if(dp[3][0] == null || dp[3][1] == null){ 

 dp[3][0] = dp[2][0] + dp[1][0]; >> 1 + 0 이므로 dp[3][0] 에 1 저장 

 dp[3][1] = dp[2][1] + dp[1][1]; >> 1 + 1 이므로 dp[3][1] 에 2 저장

}

return dp[3];  >> 반환

 

fibonachi(3) 결과 dp[3]을 반환받아서 System.out.println(dp[3][0] + " " + dp[3][1]); 을 출력하면 1 2 결과를 얻는다.

○ 결과