[자료구조] 동적계획법(DP)

동적 계획법

동적 계획법의 개념

• 한 가지 문제에 대해 단 한 번만 풀도록 하는 알고리즘
• 똑같은 연산을 반복하지 않도록 함
• 복잡한 문제를 더 작은 하위 문제로 나누어 해결
• 중복 계산을 줄여서 계산 속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산 가능

 

동적 계획법의 조건

• 겹치는 부분 문제 (Overlapping Subproblems)
  • 동일한 작은 문제들이 반복하여 나타나는 경우 사용 가능
  • 부분 문제의 결과를 저장하여 다시 계산하지 않을 수 있어야 함
  • 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하여 부분 문제가 중복되지 않는 경우 사용 불가
• 최적 부분 구조 (Optimal Substructure)
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능
  • 작은 부분 문제에서 구한 최적해로 합쳐진 큰 문제의 최적해를 구할 수 있어야 함
  • 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일

 

동적 계획법 구현

1. Bottom-Up

• 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식
• 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결
• 이를 위해 반복문을 사용하여 반복적으로 부분 문제들을 해결하고 결과를 배열 등에 저장
• 일반적으로 더 직관적이고 이해하기 쉬움
• 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장함

    public int fibonacci(int n) {

        int n1 = 0;
        int n2 = 1;
        int next = 0;

        if (n <= 1) {
            return n;
        }


        for (int i = 0; i < n - 1; i++) {
            next = n1 + n2;
            n1 = n2;
            n2 = next;
        }

        return next;
    }

 

2. Memoization

• 큰 문제를 작은 부분 문제로 나누어 해결하는 방식
• 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 할 수 있음
• 재귀 함수를 사용
• 문제를 작은 부분 문제들로 나누고, 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 memoization을 활용
• 캐싱을 통해 이전 계산 결과를 저장하여 중복 계산을 피하는 것을 의미
• 재귀를 사용하여 구현이 더 간단
• 재귀 호출의 오버 헤드가 발생할 수 있음
• 모든 작은 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있음

    public static int[] memo = new int[100];

    public int fibonacci(int n) {
        if (memo[n] > 0) {
            return memo[n];
        }

        if (n <= 1) {
            memo[n] = n;
            return memo[n];
        } else {
            memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
            return memo[n];
        }
    }