동적계획법 (Dynamic Programming)

동적계획법 (Dynamic Programming)

• 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법

메모이제이션(Memoization)

• 제귀 함수 호출시 중복으로 호출하는 부분을 줄이고자 결과값을 기록하고, 그 기록한 값을 참조하는 것
• 높은 수에서 낮은 수 (구하려는 n번째 식을 구하기 위해 n - 1, n - 2번째 값을 구하려고 하므로)로 내려가기 때문에 탑다운 방식 (Top-Down)

피보나치 수2

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

Memoization code

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

/**
*	시간 : 64ms, 메모리 : 11,516KB
*/
public class Main {
    static int N;
    static long[] dp = new long[91];
    static long ret;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        System.out.println(fibo(N));
        br.close();
    }
    static long fibo(int index){
    	// 기저 사례
    	if(index <= 1) return dp[index] = index;
        
        // 값이 저장되어 있지 않다면 점화식을 이용하여 값을 찾는다
        if(dp[index] == 0) dp[index] = fibo(index-1) + fibo(index-2);
        
        // 값이 저장되어 있다면 바로 값을 반환
        return dp[index];
    }
}

Tabulation

• for문을 이용하는 방법으로, 순서대로 배열에 값을 채워나가는 방식
• 아래에서 값을 채워 나가기 때문에 바텀업 방식 (Bottom-Up)
• 이론적인 시간복잡도는 두 방법(Top-Down, Bottom-Up)이 동일하나, 탑다운 방식은 함수를 재귀적으로 여러번 실행해야 하므로 함수 처리에 추가적인 시간이 약간 더 붙어 실제로는 바텀업 방식이 약간 더 빠릅니다.

Tabulation code

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

/**
*	시간 : 64ms, 메모리 : 11,532KB
*/
public class Main {
    static int N;
    static long[] dp = new long[91];
    static long ret;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= N; ++i){
        	dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(dp[N]);
        br.close();
    }
}