DP(동적계획법) - 백준_1003번 피보나치 수열

DP(Dynamic Programming) - 동적계획법

개요

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

(한번 해결한 문제에 대한 답을 활용하는 방법)

 

사용하는 이유

일반적인 재귀 함수를 예로 들었을 때, 대표적으로 피보나치 수열을 보면

f(n) --> f(n-1) + f(n-2) 의 구조를 갖는다.

이때에 내가 f(100)의 값을 구하면 그 과정에서 중복되는 과정이 존재하게 되는데, 이때의 값을 저장하고 사용한다면 효율이 달라질 것이다.

 

 

출처: https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

---

 

백준 - 1003번 피보나치 수열

앞서 언급된 "동적 계획법"을 내가 이해하기 위한 문제이다.

 

결국은 N 값의 피보나치 수열을 수행했을 때, 0과 1의 함수가 각각 몇번 호출되는지를 구하는 문제이다.

 

 

코드 전문

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class num_1003 {
	static int val_0 = 0;
	static int val_1 = 0;
	static Map<Integer, int[]> memory_val = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int val_T = Integer.parseInt(st.nextToken());
		
		for(int i=0; i< val_T; i++) {
			val_0 = 0;
			val_1 = 0;
			st = new StringTokenizer(br.readLine());
			int vat = Integer.parseInt(st.nextToken());
			fibonacci(vat);
			bw.write(val_0 + " " + val_1+"\n");
		}
		
		br.close();
		bw.close();
	}
	
	
	private static void fibonacci(int n) {
		if (n == 0) {
			val_0++;
	    } else if (n == 1) {
	    	val_1++;
	    } else if(memory_val.getOrDefault(n, null) != null){
	    	int[] val_arr = memory_val.get(n);
	    	val_0 += val_arr[0];
	    	val_1 += val_arr[1];
	    }else {
	    	fibonacci(n-1);
	    	fibonacci(n-2);
	    	memory_val.put(n, new int[]{val_0, val_1});
	    }
		
	}

}

 

나의 경우 0과 1이 몇번 호출되는지를 갖는 전역 변수 2개와, 피보나치 수열 각 경우의 0,1 값을 갖는 map을 선언하여 풀이했다.

 

만든 map에 값이 있다면 그 값을 호출하여 사용하고, 없다면 값을 구하여  put하는 식으로 써내려갔다.

 

 

** 나는 map을 사용했지만... 굳이 map이 아니라 배열로 풀면 더 좋은 성능을 내는 코드가 된다... 예로

memory_arr 이라는 2차원 배열을 선언하고 값을 저장한다면,

 

memory_arr[N][0or1] = ??

 

처럼 N번째의 피보나치 수열에서 0과 1의 호출 값을 각각 저장한다면 map과 전역변수 2개를 활용하는 것 보다 나은 성능을 보여줬다..

공부하자