동적 계획법(Dynamic Programming : 기억하며 풀기) -1

728x90

📌 동적 계획법(Dynamic Programming)

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

동적이라는 말을 쉽게 말하자면 답을 재활용하는 것이다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하는 등 알고리즘이라기 보다는 문제를 해결하기 위한 하나의 방법론과 같다. 동적 계획법은 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다.

❗️피보나치 수열을 예로 들어보자

피보나치 수열은 위와 같은 구조로 재귀 함수를 통해 구현된다.

즉, 값이 1인 fib(0)과 fib(1)을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다.

하지만 인덱스의 값이 커질수록 호출되는 재귀함수가 무궁무진하게 커지는 문제가 발생한다.

피보나치 트리의 구조를 자세히 살펴보면 빨간색 부분이 중복되는 것을 알 수 있다. 이처럼 중복되는 요소를 제거하여 보다 효율적인 알고리즘을 이용하는 것이 바로 동적 계획법(Dynamic Programming)이다.

✔️ DP 문제가 성립할 조건

최적 부분 구조(Optimal Substructure)

상위 문제를 하위 문제로 나누어 하위 문제의 답을 모아 상위 문제를 해결이 가능한 경우

중복되는 부분 문제(Overlapping Subproblem)

동일한 작은 문제를 반복적으로 해결해야하는 경우

정확한 정답(Correct Answer)

문제의 크기에 관계없이 특정 문제에 대한 정답이 항상 일치하는 경우

📌 Bottom-Up 방식(상향식)

가장 작은 문제에서부터 시작해서 문제를 해결하여 그 값을 저장(Tabulation)하고, 계산된 값을 재활용하여 전체 문제를 해결하는 구현 방식

다음은 Bottm-Up 방식을 이용해 피보나치 수열을 구현한 코드이다.

public class BottomUpFib {

    static int[] fib;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        fib = new int[N+1];
        System.out.println(fibonacci(N));
    }

    static int fibonacci(int N) {
        fib[1] = 1;
        fib[2] = 2;
        for (int i = 3; i < N+1; i++) {
            fib[N] = fib[N-1] + fib[N-2];
        }
        return fib[N];
    }
}

📌 Top-Down 방식(하향식)

전체 문제에서부터 시작해서 가장 작은 문제까지 재귀적으로 호출한 뒤 해결한 값을 저장 및 기억(Memorization)하여 결과 값을 재활용하는 방식

다음은 Top-Down 방식을 이용해 피보나치 수열을 구현한 코드이다.

public class TopdownFib {

    static int[] fib;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        fib = new int[N+1];
        System.out.println(fibonacci(N));
    }

    static int fibonacci(int N) {
        if (N==1 || N==2) return 1;
        if(fib[N] != 0) return fib[N];
        fib[N] = fibonacci(N - 1) + fibonacci(N - 2);
        return fib[N];
    }
}

📌 메모리제이션(Memorization)

동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내씀으로서 중복 계산을 방지할 수 있게 하는 기법

앞서 구현한 코드에서 볼 수 있듯이 Bottom-Up 코드와 Top-Down 코드에서 공통적으로 static 키워드의 배열 int[] fib에 값이 저장된다. 한 번 계산한 결과 값은 재활용되고 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 획기적으로 감소하는 것을 알 수 있다.

✔️ 메모리제이션 특징

같은 문제를 다시 호출해 결과 값을 재활용 할 수 있다.
값을 기록해 놓는다는 점에서 캐싱(Caching)이라고 한다.
DP에만 국한된 개념은 아니다.

📌 동적 계획법(Dynamic Programming) vs 분할 정복 (Divide and Conquer)

숫자 배열 중 최대 합을 갖는 구간 찾기 같은 예를 들어보자면 O(N^3)짜리 시간복잡도 알고리즘을 분할 정복법으로 O(N*LogN) 정도의 시간 복잡도를 만들 수 있다. 여기서 더 나아가 동적계획법(Dynamic Programming)을 사용하면 O(N)의 시간복잡도 알고리즘을 만들 수 있다. 그러나 문제가 복잡해지면 풀이가 직관적으로 떠오르지 않아 어렵고 대부분의 문제는 분할 정복법으로도 풀린다. 다만, 알고리즘 대회와 같이 '시간 제한'이 짧은 문제가 많은 경우 동적 계획법(Dynamic Programming)으로 풀어야 한다.

❗️둘의 차이점은 하위 문제의 중복이다.

분할정복은 동일한 하위 문제에 대해서도 계산을 하기 때문에 하위 문제가 독립적이지 않고 중복되는 경우에는 동적 계획법(Dynamic Programming)의 방식이 더 나은 시간복잡도를 가진다.

📌 일반적인 동적 계획법(Dynamic Programming) 사용처

3항 이상의 재귀 수열
0-1 배낭 문제(0-1 Knapsack Problem) : 견딜 수 있는 무게가 제한된 배낭에 가장 많은 가치의 물건을 넣기
가장 긴 증가 수열 문제(LIS Problem) : 아무 수열이나 주고, 순서를 바꾸지 않은 상태로 뽑아서 만들 수 있는 가장 긴 증가수열의 길이 구하기
연쇄 행렬 곱셈 문제 : 주어진 연쇄행렬들의 곱셈을 각 원소의 곱셈 횟수를 최소로 할 수 있는 행렬곱셈의 순서를 찾는 최적화 문제
그래프 상의 최단거리 문제(밸먼-포드 알고리즘, 플로이드-위셜 알고리즘)

오늘도 런캣은 달린다

동적 계획법(Dynamic Programming : 기억하며 풀기) -1