동적 프로그래밍

by

동적 프로그래밍

데이터 구조의 동적 할당에서 ‘동적’은 프로그램이 실행되는 동안
실행에 필요한 메모리를 할당하는 기술입니다.

그러나 알고리즘의 동적 프로그래밍에서 ‘동적’큰 의미는 없고 그냥 ‘기억’이라고 생각하면 편하다.

동적 프로그래밍에서 ‘프로그램 작성’테이블을 생성하는 것을 의미합니다.

간단히 말해서, 이전에 얻은 값기반으로 규칙성을 파악하다그래서 다음 값을 얻기 위해당신은 그것을 생각할 수 있습니다

알고리즘 설계 기법(패러다임) 중 하나이다

하부 문제의 최적 솔루션을 적절하게 사용하여 상부 문제 해결이렇게 하면 불필요한 계산을 줄일 수 있습니다.

DP 알고리즘 기법이란?

DP 알고리즘 기법은 이미 계산된 결과(하위 문제)를 별도의 메모리 영역에 저장하고,
재계산하지 않도록 설계하여 메모리를 적절하게 사용하고 실행 시간을 획기적으로 개선합니다.

일반적으로 두 가지 유형의 DP 구현 방법이 있습니다.

하향식(top-down)과 상향식(bottom-up)으로 구성된다.

DP 성립 조건

단순 재귀 코드보다 효율이 높은 코드를 설계할 수 있습니다.

최적의 하부 구조

  • 상위 문제는 하위 문제로 나눌 수 있으며 상위 문제는 하위 문제의 답을 모아서 해결할 수 있습니다.
  • 이러한 구조의 대표적인 경우가 특정 경유지를 통해 목적지로 가는 문제이다.

겹치는 하위 문제

  • 같은 작은 문제를 반복해서 해결해야 합니다.
  • 따라서 피보나치 수열은 DP를 사용하기 위한 조건을 만족합니다.

겹치는 부분 문제의 예

피보나치 수열을 구현하려고 합니다.

재귀식은 F(n) = F(n-1) + F(n-2)이므로 간단한 재귀함수로 구현한다.

public class Simple {
    public static void main(String() args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dp = new int(n+1);
        System.out.println(fibonazzi(n));
    }

    // 단순 재귀
    static int fibonazzi(int x) {
        if (x == 1 || x == 2) return 1;
        return fibonazzi(x-1) + fibonazzi(x-2);
    }
}

위와 같이 메모이제이션을 사용하지 않으면 같은 함수가 반복적으로 호출되며,
재귀적 방법으로 구현할 때 시간 복잡도는 O(2^n)입니다.

아래 그림과 같이 매우 비효율적인 구조임을 알 수 있습니다.

이미지-20230330070434190

위에서 아래로

상위 문제를 해결하기 위해 하위 문제를 재귀적으로 호출하여 하위 문제를 해결함으로써,

위의 문제를 해결하는 방법입니다.

이때 해결된 하위 문제를 저장하기 위해 메모이제이션을 사용합니다.

피보나치 함수를 구현할 때 하향식은 재귀 호출을 사용하여 구현됩니다.

/* DP 하향식 */
public class TopDown {
    static int() dp;

    public static void main(String() args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dp = new int(n+1);
        System.out.println(fibonazzi(n));
    }

    // Top-down
    static int fibonazzi(int x) {
        if (x == 1 | x == 2) return 1;
        if (dp(x) != 0) return dp(x);

        dp(x) = fibonazzi(x-1) + fibonazzi(x-2);
        return dp(x);
    }

상향식

앞에서 계산한 문제의 값을 사용하여 상향식으로 문제를 풀고,

상향식은 상위 수준 문제를 해결하는 방법으로 DP의 전형적인 형태입니다.

여기서 사용되는 문제 결과 값을 저장하기 위한 목록을 DP 테이블이라고 합니다.

상향식 방법은 루프문을 사용하여 구현됩니다.

/* DP 상향식 */
public class BottomUp {
    static int() dp;

    public static void main(String() args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dp = new int(n+1);
        System.out.println(fibonazzi(n));
    }

    // Bottom-up
    static int fibonazzi(int x) {
        dp(1) = 1;
        dp(2) = 1;

        for (int i=3; i<x+1; i++) {
            dp(i) = dp(i-1) + dp(i-2);
        }
        return dp(x);
    }
}

메모이제이션

DP 구현 방법 중 하나로 연산 결과를 메모리 공간에 한번 메모해 두는 기법이다.

이것을 사용하면 모든 하위 문제가 한 번만 평가된다는 것을 보장하기 때문에
함수 호출 횟수를 대폭 줄일 수 있습니다.

/* DP Memoization */
public class Memoization {

    static int() dp;

    /* 일반 재귀 함수
     - 중복된 계산을 반복해서 하게 된다.
     - 시간복잡도는 O(2^n)으로 x의 수가 커질수록 복잡도가 기하급수적으로 커진다.
     */
    static int fibonazzi(int x) {
        if (x == 1 | x == 2) return 1;
        return fibonazzi(x-1) + fibonazzi(x-2);
    }

    /* Memoization
     - 하위 문제의 결과 값을 dp()배열에 저장해놓고 필요할 때마다 계산된 값을 호출한다.
    */
    static int memo(int x) {
        if (x == 1 | x == 2) return 1;
        if (dp(x) != 0) return dp(x);
        dp(x) = memo(x-1) + memo(x-2);
        return dp(x);
    }
}

메모이제이션 기능

  • 같은 문제를 다시 호출하면 메모한 결과를 다시 불러옵니다.
  • 값을 기록한다는 점에서 캐싱과 유사하며 캐싱이라고도 합니다.
  • DP에만 국한된 개념이 아닙니다.
  • 한 번 계산된 결과만 포함되며 DP 이외의 방법으로 사용할 수 있습니다.

동적 프로그래밍과 분할 정복

분할 정복 방법을 사용하여 최적의 하위 구조를 풀 수 있습니다.

DP와 Divide-and-conquer는 문제가 최적의 하위 구조 조건을 가질 때 사용할 수 있습니다.

더 작은 하위 문제로 나누어 문제를 해결하십시오.

이 둘의 가장 큰 차이점은 하위 문제의 중복 발생 여부입니다.

하위 문제가 독립적이지 않고 중첩되는 경우 DP 방법이 분할 정복보다 시간 복잡도가 더 좋습니다.

분할 정복에서는 동일한 하위 문제가 독립적인 구성이므로 반복적으로 계산할 수 없습니다.

이미지-20230330121046690