1003 : 피보나치

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

이번에 분석해볼 코드는 피보나치 수열이다.

이 문제는 동적 프로그래밍을 이용해서 문제를 풀어내는 알고리즘을 써야만 하는데,

실제로 피보나치 수열을 재귀적 형식으로 풀어내는 방식을 차용했더니, 시간 초과가 났다.

 

그럴 수 밖에...재귀는 문제를 풀기 위한 함수가 들어가면 들어갈 수록 스택에 쌓이고 return 값이 반환이 되지 않으면 Stack Overflow가 난다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

문제의 재귀 코드

예를 들어  fibonacci(100)을 하게 된다면 fibo(99)+fibo(98) -> fibo(99)=fibo(97)fibo(98) 로 각 재귀함수가 전개될 때마다 두개의 풀어야할 재귀 함수가 생긴다.

 

(처음엔 시간 초과의 문제가 단순하게 자바 언어의 특성인 줄 알고, Vector나 ArrayList를 배열로 바꿔서 풀어보려고 했으나 이 문제가 아니었음을 알고 나서, 풀게 되었다)

 

다이나믹 프로그래밍에서 Recursive 방식으로 문제를 풀고자 할 때, 거의 필수적으로 사용해줘야하는 알고리즘이 있다.

Memoization이다

 

Memoization 기법을 사용해서 풀어주지 않을 경우 함수가 여러 번 중첩될 경우 해당 Function call을 호출하기 위한 Stack이 Overflow가 나게 되고, 이로 인해 오류가 생기게 된다.

 

위 방식을 해결하기 위해 ArrayList나 일반 배열, Hash등을 이용해서 이미 나온 값에 대해서는 Memo를 해주는 것이다.

 

<코드 설명>

코드는 Fibo함수와 main 함수로 쪼개서 풀었다.

Fibo 함수에서는 ArrayList를 사용해서 ArrayList 0번째,1번째에 각각 0과 1을 넣고, 0이 호출된 횟수와 1이 호출된 횟수를 세주기 위해 각각 zerocount 변수와 onecount 변수를 사용한다.

답이 될 Answer 배열을 호출해주고,

N==0일때, N==1일때, Answer의 0번째 변수가 zerocount 1번째 변수가 onecount로 지정되게 하였고,

가장 중요한 부분은 else이다

다음 수를 찾기 위해서 그 이전의 수를 ArrayList에 넣어 더하게 만들어 이전 수를 ArrayList에 저장되게 하였다.

이 문제 풀었을 때 코드를 조금만 바꿔도 시간 초과가 났었는데 그 때문에 사기당한 거 같았다..

아래는 최종적으로 맞은 코드이다.

import java.util.*;
import java.io.*;
public class Main {

	public static int[] fibo(int N)
	{
		int Answer[]=new int[2];
			
			ArrayList<Integer> Fibo=new ArrayList<Integer>();
			Fibo.add(0);
			Fibo.add(1);
			
			int zerocount=0;
			int onecount=0;
			
			if(N==0)
			{
				zerocount++;
				Answer[0]=zerocount;
				Answer[1]=onecount;
				return Answer;			
			}
			else if(N==1)
			{
				onecount++;
				Answer[0]=zerocount;
				Answer[1]=onecount;
				return Answer;
			}
			else 
			{
				for(int i=2;i<N+1;i++)
				{
					int next=Fibo.get(i-1)+Fibo.get(i-2);
					Fibo.add(next);
				}
				Answer[0]=Fibo.get(Fibo.size()-2);
				Answer[1]=Fibo.get(Fibo.size()-1);
				
				return Answer;
			}
		
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		
		int T=Integer.parseInt(br.readLine());	
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<T;i++)
		{
			int N=Integer.parseInt(br.readLine());			
			sb.append(fibo(N)[0]+" "+fibo(N)[1]+"\n");					
		}
		System.out.println(sb);
		br.close();
	}
}