[Algorithm] - Dynamic Programming 알고리즘

 

dp 알고리즘

참고: https://hongjw1938.tistory.com/47

 

DP, 즉 Dynamic Programming(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

 

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

 

피보나치 수를 재귀로 함수를 구성하면 

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

⇒ f(n-1)에서 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문

 

한번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면?

 

⇒ dp

O(n^2)→O(f(n))로 개선

 

- dp의 사용조건: 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능

---

1. Overlapping Subproblems(겹치는 부분 문제)

⇒ 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

위의 그림과 같이 중복되는 부분이 있어야 한다.

---

2. Optimal Substructure(최적 부분 구조)

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

⇒ 즉, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때

 

📍 dp 사용하기

1) dp로 풀 수 있는 문제인지 확인

: 보통 특정 데이터 내 최대화/ 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률등의 계산에 많이 사용

 

2) 문제의 변수 파악

: 문제 내 변수의 개수를 알아내야 한다는 것 (state 결정)

 

3) 변수 간 관계식 만들기 (점화식)

 

4) 메모하기

: 변수의 값에 따른 결과를 저장

 

5) 기저 상태 파악하기

: 가장 작은 문제의 상태를 알아야 함 (피보나치 수열에 f(0)=0, f(1)=1 과 같은 방식)

 

6) 구현하기

1.   Bottom-Up (Tabulation 방식) - 반복문 사용
2.   Top-Down(Memorization 방식) - 재귀 사용

 

• Bottom-Up 방식

: 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식

dp라는 배열이 있고 1차원으로 가정했을 때, dp[0]이 기저상태고 dp[n]을 목표 상태라고 하자.

Bottom-Up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

 

🔎 왜 Tubulation?

반복을 통해 dp[0]부터 하나하나씩 채우는 과정을 “table-filling”이라 하며, 이 table에 저장된 값에 직접 접근하여 재활용하므로 Tubulation이라 한다.

 

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];
    }

 

 

• Top-Down 방식

dp[0]의 기저상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

 

이미 이전에 계산을 완료한 경우에 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memorization 이라고 부른다.

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];
    }

 

• 분할정복과의 차이점은?

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

 

But, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 사용

⇒ 동일한 중복이 일어나면 동적 프로그래밍 사용

 

병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결