baekjoon 1003번 (피보나치 함수)
-
문제파악
java baekjoon 1003번은 피보나치 수열을 돌리며 0과 1을 return한 횟수를 결과로 반환해야하는 문제이다.시간제한 : 0.25
메모리 제한 : 128MB
- 시간복잡도를 고려하지 않은 코드
idea) 재귀를 사용해서 n==0일때 0을 return하고 n==1일때 1을 return한다.
import java.util.Scanner;
public class Main {
static int countOne = 0;
static int countZero = 0;
public int fibo(int n){
if(n==0){
countZero += 1;
return 0;
}else if(n==1){
countOne += 1;
return 1;
}else{
return fibo(n-1)+ fibo(n-2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=0; i<n; i++){
int result = new Main().fibo(sc.nextInt());
System.out.println(countZero + " " + countOne);
countZero = 0;
countOne = 0;
}
}
}
해당 코드는 피보나치 수열 그 자체를 보여준다.
다만, 위와같이 작성한다면 재귀를 돌 때마다 연산이 증가한다.
fibo(n-1) + fibo(n-2)를 보자.
재귀적으로 자신을 호출하며 피보나치 수열을 계산하는데, 이과정에서 각각의 호출마다 다시 두 번의 호출이 수행되도록한다. n번째 항을 계산하기 위해서는 총 2^n번의 호출이 수행된다.
따라서, 빅오표기법에 의해 코드의 시간복잡도는 O(2^n)이다.
1초가 걸릴때의 입력의 최대 크기를 보면,O(2^n)이라면 대략 20정도까지를 최대크기로 생각해야한다.
심지어 해당문제에서는 1초 시간제한도 아니고 0.25초이기에 위의 코드는 다른 방법을 사용해야한다.
- 시간복잡도를 고려한 후
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dp = new int[42];
dp[0] = 1;
dp[1] = 0;
for(int j=2; j<42; j++){
dp[j] = dp[j-1] + dp[j-2];
}
for(int i=0; i<n; i++){
int num = sc.nextInt();
System.out.println(dp[num] + " " + dp[num+1]);
}
}
피보나치 함수는 이전 두항을 사용한다는 규칙이 존재하는데, 이를 이용한다면 동적계획법으로 단순히 반복문을 사용한 코드로 변경이 가능하다.
dp를 사용한다.
idea)
dp[0]에는 0이 나오는 횟수 0을 넣어두고 dp[1]에는 입력받은 숫자가 0일때의 1의 횟수를 저장한다. => num이 0일때는 dp[0]과 dp[1]을 차례대로 입력받는다.
일반화 : dp[num]일때 0의 횟수는 dp[num] 이고 1의 횟수는 dp[num+1] 이다.
위의 코드로 변경함으로써, O(N)의 시간복잡도를 가지게 되었다. n번만큼 dp[j-1] + dp[j-2] 을 단순 계산하기 때문에 O(N)이다.
O(N)이면 시간제한이 1초일때 약 1억정도의 크기가 가능하다고 생각하면 된다.
추가로 공간복잡도에 대해서 알아보자.
수정한 코드를 기준으로 보면 공간복잡도는 O(1)이다. 배열 dp는 고정된 크기 42의 정수를 저장하기에 n의 영향을 받지 않는다. 배열의 크기가 일정하다. 따라서 O(1)로 일정하다.
n이 42로 고정이고 int는 하나에 4 바이트의 크기를 가지기 때문에 128MB(128*10^6)의 제한에는 충분히 감당 가능 할 것이다.
