(코테) 백준_1003_피보나치 함수 (DP)

 

 

내가 최초 제출한답 (DP 사용 X )

import java.util.*;
import java.io.*;

public class Main {
	static int T;
	static int N;
	static int count0 =0 ,count1 =0;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T=Integer.parseInt(st.nextToken());
		
		//T번 순환   
		for(int i=0;i<T;i++) {
			count0=0; 
			count1=0;			
			 N=Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());			 
			
			dfs(N);
			System.out.println(count0 + " "+count1);						
		}				
	}

	
	public static void dfs(int N) {
		if(N<0) return;
		//종료 조건 0 혹은 1
		if(N==0) {
			count0++;
			return;
		} 
		if(N==1) {
			count1++;
			return;
		}		
		
		dfs(N-1);
		dfs(N-2);
		
	}
}

 

 

 

 

이후 개선 한 답.

package test;

import java.util.*;
import java.io.*;


public class Backjun_1003_test {

	static int T;
	static int map[][] = new int[41][2];
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
						
		T= Integer.parseInt(st.nextToken());
		
		map[0][0] = 1; 	map[1][0] = 0;		
		map[0][1] = 0;  map[1][1] = 1;

		for(int i=2;i<41;i++) {
			map[i][0] = map[i-1][0] + map[i-2][0];
			map[i][1] = map[i-1][1] + map[i-2][1];
		}
		
		
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			
			
			System.out.println(map[N][0]+" "+map[N][1]);
			
			
		}
		
		
	}

}

 

 

 

회고.

return fibonacci(n‐1) + fibonacci(n‐2);

 

1. 피보나치 함수를 형태를 보고 단순 DFS를 생각을 했다. (시간 초과)

  -> 깊이가 깊을때 DFS로 하게되면 불필요한 중복 호출 + N값이 많으면 효율이 극대로 떨어질 수 있따는 것을 인지를 늦게 하였다.

문제점 및 느낀 점

• 중복 호출 문제:
  재귀로 피보나치 함수를 구현하니, 동일한 함수 호출이 여러 번 발생한다.
  예를 들어, dfs(3)를 호출하면 dfs(2)와 dfs(1)을 호출하고,
  그 중 dfs(2)가 다시 dfs(1)과 dfs(0)을 호출하는 등,
  불필요한 연산이 반복되었다.
• 효율성 저하:
  N의 값이 커질수록 중복 호출이 기하급수적으로 늘어나 시간 초과를 일으킨다.
  이를 통해 재귀의 한계를 깨달았고,
  빠른 시간 내에 답을 도출해야 할 때 **DP(동적 계획법)**의 필요성을 인식하게 되었다.

 

 

 

 

 

2. DP로 map[N][0],  map[N][1] 이중 배열로 특정 인덱스일때  0의 개수,1의 개수 저장하는 방식으로 중복 함수 호출을 방지하였다

개선 포인트

• DP 배열 사용:
  이중 배열 map[i][j]를 사용해,
  i번째 피보나치 호출시 0과 1이 몇 번 호출되는지를 저장했다.
  • map[i][0]: fibonacci(i) 호출 시 0이 출력된 횟수
  • map[i][1]: fibonacci(i) 호출 시 1이 출력된 횟수
• Bottom-Up 접근법:
  0과 1에 대한 기저 조건을 먼저 저장하고,
  2부터 40까지 순차적으로 이전 두 값의 합을 구함으로써
  중복 계산 없이 필요한 값을 미리 계산해두었다.
• 출력 형식 정확성:
  각 테스트 케이스마다 결과를 한 줄씩 출력함으로써,
  출력 형식 오류를 방지하였다.