[Algorithm] 동적 계획법(Dynamic Programming, DP)

haeny-dev·2021년 8월 1일

algorithm algorithm - 동적 계획법(Dynamic Programming, DP)

Algorithm

목록 보기

3/3

🖥 동적 계획법(Dynamic Programming)

동적계획법(Dynamic Programming, DP) 은 큰 문제를 작은 문제로 나누어서 푸는 방법을 말한다.

이 방법은 부분 문제 반복(Overlapping Subproblem)과 최적 부분 구조(Optimal Substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

➕ 부분 문제 반복

부분 문제 반복(Overlapping Subproblem) 은 어떤 문제가 여러 개의 부분 문제(subproblem)으로 쪼개질 수 있을 때 사용하는 용어이다.

이 때 '부분문제' 란, 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가리킨다.

대표적인 예로 피보나치 수를 들 수 있다. 피보나치 수열은 이전 두 수를 더한 수가 다음 수가 되는 수열이다.

N번째 피보나치 수 = N-1번째 피보나치 수 + N-2번째 피보나치 수
N-1번째 피보나치 수 = N-2번째 피보나치 수 + N-3번째 피보나치 수
N-2번째 피보나치 수 = N-3번째 피보나치 수 + N-4번째 피보나치 수

수식으로 표현하면, 아래와 같습니다.

$f(n) = f(n-1) + f(n-2)$
$f(n-1) = f(n-2) + f(n-3)$
$f(n-2) = f(n-3) + f(n-4)$

f(n)를 구하기 위해서는 f(n-1) 과 f(n-2) 가 필요합니다. 여기서 f(n-2) 는 이미 f(n-1) 을 구하는 과정에서 값을 구한 문제입니다.

또한 f(n)의 f(n-1) 구하는 과정은 f(n) 을 구하는 방식과 같아 재귀 알고리즘으로 해결된다는 것을 확인할 수 있습니다.

이와 같이 사용되었지만 다시 재사용되거나 재귀를 통해서 해결되는 문제들이 반복되는 것을 부분 문제 반복이라 합니다.

➕ 최적 부분 구조

최적 부분 구조(Optimal Substructure)는 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로 설계될 수 있는 경우를 말한다.

즉, 최적 부분 구조일 때 문제의 정답을 작은 문제의 정답에서부터 구할 수 있음을 말한다.

예를 들어, 가장 빠른 경로를 찾는 문제를 들 수 있다.

문제
→ 서울에서 대전을 거쳐 부산까지 가는 가장 빠른 경로를 찾아라.

부분문제
서울에서 대전까지 가는 가장 빠른 경로를 찾아라.
→ 서울 > 광명 > 대전
대전에서 부산까지 가는 가장 빠른 경로를 찾아라.
→ 대전 > 대구 > 부산

해결
서울에서 대전까지 가장 빠른 경로 + 대전에서 부산까지 가장 빠른 경로
→ 서울 > 광명 > 대전 > 대구 > 부산

➕ 메모이제이션(Memoization)

위의 피보나치 수를 다시 보면, N번째 피보나치 수를 구한다고 가정해보자.

$f(N) = f(N-1) + f(N-2)$
$f(N-1) = f(N-2) + f(N-3)$
$f(N-2) = f(N-3) + f(N-4)$
$...$
$f(2) = f(1) + f(0)$
$f(1) = 1$
$f(0) = 0$

여기서, f(N) 을 구할 때, 사용 된 f(2) 의 값이나, f(N-1) 을 구할 때 사용 된 f(2) 의 값, f(N-2) 을 구할 때 사용 된 f(2) 의 값은 모두 같다.

이와 같이 각 문제에서 사용되는 부분문제가 겹치는 경우 같은 문제의 값을 매번 구하는 것은 비효율적이다. 이를 해결할 수 있는 방법이 메모이제이션(Memoization) 이다.

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

➕ 구현

동적 계획법의 구현 방식에는 두 가지 방법이 있다.

Top-down 은 큰 문제를 작은 문제로 쪼개면서 풀어나가는 방식이고,
Bottom-up 은 작은 문제부터 차례대로 풀어 나가는 방식이다.

1. Top-down

public class Fibonacci {

    private int n;
    private int[] fibonacciMemory;

    public Fibonacci(int N){
        this.n = N;
        this.fibonacciMemory = new int[N + 1];
    }

    public int getFiboByTopdown(){
        return fibo(n);
    }

    private int fibo(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(fibonacciMemory[n] != 0) return fibonacciMemory[n];
        return fibo(n-1) + fibo(n-2);
    }
}

2. Bottom-up

public class Fibonacci {

    private int n;
    private int[] fibonacciMemory;

    public Fibonacci(int N){
        this.n = N;
        this.fibonacciMemory = new int[N + 1];
    }
    
    public int getFiboByBottomup(){
        if(n == 0) return 0;
        if(n == 1) return 1;

        fibonacciMemory[0] = 0;
        fibonacciMemory[1] = 1;
        for(int i = 2; i <= n; i++){
            fibonacciMemory[i] = fibonacciMemory[i-1] + fibonacciMemory[i-2];
        }
        return fibonacciMemory[n];
    }
}