[알고리즘] 동적 계획법(DP) 📌

동적 계획법 (Dynamic Programming)

• 동적 계획법은 다이나믹 프로그래밍(DP)라고도 불린다
• 이는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로, 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다
• 쉽게 생각하면 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하기 떄문에 '구한 값은 기억하며 푸는 방법'이다

 

 

 

DP를 사용하는 이유

• DP는 일반적인 재귀 방식과 매우 유사하다
• 그러나 일반적인 재귀를 단순히 사용 시, 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있다

 

 

🧮 대표적인 예시 : 피보나치 수열

피보나치 수열은 다음과 같다

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

 

피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 다음과 같은 점화식을 얻을 수 있다

 

f(n) = f(n-1) + f(n-2)

 

그런데 f(n-1), f(n-2) 에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고, 계속해서 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다

그렇게 되면 결국 컴퓨터가 죽는 경우가 발생할 수 있다🥶

피보나치 수열 함수 호출 트리

이 때 만약 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면 매우 효율적으로 문제를 해결할 수 있게 된다!

재귀 함수를 사용할 때와는 달리 같은 계산을 하지 않게 되므로 시간 복잡도 또한 개선이 가능하다

 

 

 

 

🤔 DP의 사용 조건

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다

1. Overlapping Subproblems (겹치는 부분 문제)
2. Optimal Substructure (최적 부분 구조)

 

 

① Overlapping Subproblems (겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과값을 재활용해서 전체 답을 구한다

따라서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다

즉, DP는 부분 문제의 결과를 저장하여 다시 계산하지 않도록 해야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하므로 부분 문제가 중복되지 않는 경우에는 사용할 수 없다

 

예를 들어 이진 탐색과 피보나치 수열의 경우를 비교해보자!

• 이진 탐색은 특정 데이터를 정렬된 배열 내에서 그 위치를 찾기 때문에 그 위치를 찾은 후 바로 반환할 뿐이지 이를 재사용하는 과정은 거치지 않는다
• 반면, 피보나치 수열은 f(n) = f(n-1) + f(n-2) 이기 떄문에 동일한 부분 문제가 중복되어 나타나기 때문에 저장된 값을 재활용할 수 있게 된다

 

 

② Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과값을 사용하여 전체 문제의 최적의 결과를 낼 수 있는 경우를 의미한다

따라서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다

 

예를 들어 A-B까지의 최단 경로를 찾는 경우를 생각해보자

만약 중간에 X가 있을 때, A-X-B 가 많은 경로 중 최단 경로라면 전체 최적 경로도 A-X-B 가 된다

• 위의 그림에서 A-X 사이의 최단 거리는 AX2이고, X-B 사이의 최단 거리는 BX2이다
• 이 때 전체 최단 경로는 AX2-BX2이다
• 다른 경로를 선택한다고 해서 전체 최단 경로가 변할 수는 없다!

 

위와 같이 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다

피보나치 수열도 동일하게 이전의 계산값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖는다

 

 

 

 

 

 

DP 사용하기

DP는 특정한 경우에 사용하는 알고리즘이 아닌, 하나의 방법론이므로 다양한 문제 해결에 사용된다

 

일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행한다

1. DP로 풀 수 있는 문제인지 확인한다
2. 문제의 변수를 파악한다
3. 변수 간 관계식을 만든다 -> 점화식
4. 계산한 값을 저장한다 -> Memoization or Tabulation
5. 기저 상태를 파악하다
6. 구현한다

 

① DP로 풀 수 있는 문제인지 확인

• 애초에 이를 판단하는 것부터 어렵다
• 우선 DP의 조건 부분에 써있듯이, 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다
• 즉, 위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크하는 것이 좋다
• 보통 특정 데이터 내 최대화/최소화 계산을 하거나 특정 조건 내 데이털르 세야 한다가나 확률 등의 계산의 경우, DP로 풀 수 있는 경우가 많다

 

② 문제의 변수 파악

• DP는 현재 변수에 따라 그 결과값을 찾고 그것을 전달하여 재사용하는 것을 거친다
• 즉, 문제 내 변수의 개수를 알아내야 하며 이를 'state를 결정한다' 라고 한다
  • 예를 들어 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다
  • 그 변수가 얼마냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다
  • 또한 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용한다
  • Knapsack 문제에서는 index, 무게로 2가지의 변수를 사용한다
• 이와 같이 해당 문제에서 어떤 변수가 있는지를 파악해야 그에 따른 답을 구할 수 있다

 

③ 변수 간 관계식 만들기

• 변수들에 의해 결과값이 달라지지만 동일한 변수값인 경우 결과는 동일하다
• 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다
• 이러한 식을 점화식이라고 부르며, 이를 통해 짧은 코드 내에서 반복 또는 재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다
• 점화식은 변수의 개수, 문제의 상황마다 모두 다를 수 있다
• f(n) = f(n-1) + f(n-2) : 이 또한 피보나치 수열의 점화식이다

 

④ 메모하기

• 점화식까지 구했다면, 변수의 값에 따른 결과를 저장해야 한다
• 이를 메모한다고 하여 Memoization 이라고 한다
• 변수 값에 다른 결과를 저장할 배열 등을 미리 만들고, 결과값이 나올 때마다 배열 내에 저장하여 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다
• 이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 다라 배열의 차원이 1~3차원 등 다양할 수 있다

 

⑤ 기저 상태 파악하기

• 이제 가장 작은 문제의 상태를 알아야 한다
• 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다
• 피보나치 수열을 예시로 들면, f(0)=0, f(1)=1 과 같은 방식이다
• 이 후 두 가지 숫자를 점화식에 대입하여 값을 구하기 때문에 가장 작은 문제는 이 2개로 볼 수 있다
• 해당 기저 문제에 대해 파악한 후 미리 배열 등에 저장해두면 된다

 

⑥ 구현하기

DP는 2가지 방식으로 구현할 수 있다

1. Bottom-Up : Tabulation 방식, 반복문 사용
2. Top-Down : Memoization 방식, 재귀 사용

 

1) Bottom-Up 방식

• 아래부터 계산하고 누적시켜서 전체의 큰 문제를 해결하는 방식
  • 예를 들어 메모를 위해서 dp라는 1차원 배열을 만들었다고 가정해보자
  • dp[0]이 기저 상태이고 dp[n]이 목표 상태라면, Bottom-Up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다
• Tabulation?
  • 앞의 '메모하기' 부분에서 Memoization이라고 했는데 Bottom-up에서는 이를 Tabulation이라고 부른다
  • 왜냐하면 반복을 통해 dp[0]부터 하나씩 채우는 과정을 'table-filling'이라고 하는데, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 핟나
  • 사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 Memoization과 거의 유사하다

 

2 Top-Down 방식

• 이는 dp[0]의 기저 상태에서 출발하는 대신, dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다
• 만약 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다
• 그래서 가장 최근의 상태 값을 메모해두었다고 하여 Memoization이라고 부른다

 

아래는 예시 코드이다

public class Fibonacci{
    // DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
    // Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
    static int[] topDown_memo; 
    static int[] bottomup_table;
    public static void main(String[] args){
        int n = 30;
        topDown_memo = new int[n+1];
        bottomup_table = new int[n+1];
        
        long startTime = System.currentTimeMillis();
        System.out.println(naiveRecursion(n));
        long endTime = System.currentTimeMillis();
        System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(topDown(n));
        endTime = System.currentTimeMillis();
        System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(bottomUp(n));
        endTime = System.currentTimeMillis();
        System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
    }
    
    // 단순 재귀를 통해 Fibonacci를 구하는 경우
    // 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
    public static int naiveRecursion(int n){
        if(n <= 1){
            return n;
        }
        return naiveRecursion(n-1) + naiveRecursion(n-2);
    }
    
    // DP Top-Down을 사용해 Fibonacci를 구하는 경우
    public static int topDown(int n){
        // 기저 상태 도달 시, 0, 1로 초기화
        if(n < 2) return topDown_memo[n] = n;
        
        // 메모에 계산된 값이 있으면 바로 반환!
        if(topDown_memo[n] > 0) return topDown_memo[n];
        
        // 재귀를 사용하고 있음!
        topDown_memo[n] = topDown(n-1) + topDown(n-2);
        
        return topDown_memo[n];
    }
    
    // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
    public static int bottomUp(int n){
        // 기저 상태의 경우 사전에 미리 저장
        bottomup_table[0] = 0; bottomup_table[1] = 1;
        
        // 반복문을 사용하고 있음!
        for(int i=2; i<=n; i++){
            // Table을 채워나감!
            bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
        }
        return bottomup_table[n];
    }
}

/*
결과
832040
일반 재귀 소요 시간 : 9

832040
Top-Down DP 소요 시간 : 0

832040
Bottom-Up DP 소요 시간 : 0
*/

 

 

Q. Top-Down과 Bottom-Up 중 어떤 것이 더 나을까?

• 이는 알 수 없다!
• 실제로 재귀는 내부 스택을 만들고 함수를 호출하는 과정이 있어보여서 반복이 더 빠를 것 같다고 느낄 수 있다
• 하지만 Top-Down을 통해 문제를 푸는 경우 점화식에 따라 불필요한 계산을 오히여 Bottom-Up보다 덜 하는 경우가 있기 때문에 궁극적으로는 알 수 없다

 

 

 

💡 분할 정복 vs DP
- 분할 정복과 DP는 주어진 문제를 작게 쪼개서 하위 문제로 해결하고, 연계적으로 큰 문제를 해결한다는 점은 동일하다
- 그러나 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰고, DP는 중복이 발생하는 경우 사용한다
- 따라서 병합 정렬은 분할 정복으로, 피보나치 수열은 DP로 해결이 가능한 것이다

 

 

 

 

---

참고)

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)