[알고리즘] Dynamic Programming

1. DP란?

DP(Dynamic Programming)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 수학자인 리처드 벨만이 1940년대에 사용하던 용어였다. 1953년, 벨만은 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 이 방법을 '동적 계획법'이라 이름붙였다.

 

이와 같은 다이나믹 프로그래밍은 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다고 알려져 있다. 

 

부분 반복 문제(Overlapping Subproblem)

예를 들면, 피보나치 수열과 같은 문제이다. 

피보나치 수열을 구하는 문제는 여러 개의 부분 문제(Subproblem)으로 쪼개질 수 있다. 

모든 문제를 부분 문제로 쪼갤 수 있고, 재귀 함수를 통해 해결 할 수 있다.

 

최적 부분 구조(Optimal Substructure)

최적 부분 구조 : 작은 부분 문제에서 구한 최적의 답으로 합쳐진큰 문제의 최적의 답을 구할 수 있어야 한다.

예를 들면, fibo(n)이 최적의 답을 구하려면 작은 부분 문제인 fibo(n-1)과 fibo(n-2)이 최적의 답을 알면 된다.

작은 부분 문제의 최적의 답으로 큰 문제의 최적의 답을 구할 수 있는 것이다.

 

2. 메모하기 (Memoization)

DP를 사용할 수 있는 조건을 확인했다면 반복되는 값들을 메모하여 사용하자

연산 과정을 줄이기 위해 메모이제이션(Memoization) 이라는 동적 프로그래밍의 개념이 도입되게 되었다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        N = Integer.parseInt(br.readLine());
        long[] memo = new long[N+2];
        memo[0] = 0;
        memo[1] = 1;
        if(N >= 2) {
            for(int i = 2; i <= N; i++) {
                memo[i] = memo[i-1] + memo[i-2];
            }
        }
        System.out.println(memo[N]);

    }
}

이처럼 메모해두고 가져와서 사용하게 되면 속도 향상에 큰 영향을 준다!!

 

3. 구현하기

하향식과 상향식이 있다. 

 

① Bottom-Up 방식 (반복문을 사용)

이름에서 보이듯이, 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

 

② Top-Down 방식 (재귀를 사용)

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.