(C++) 동적 계획법 Dynamic Programming

나동빈님 블로그 참고함

weeklyps 참고함

👩🏼 동적 계획법이란? (Vs. 분할 정복)

• 상당수의 분할 정복 기법(큰 문제를 작은 여러개의 문제로 나누어 푸는 기법으로 재귀적 성격을 띔)은 동일한 문제를 추후 다시 푼다는 단점을 가지고 있다.
  • 병합정렬이나 퀵정렬 같은 분할 방식은 [1, 4] [2, 3] 이런식으로 교집합이 없는 두 집합으로서 쪼개서 따로 따로 문제를 풀게 되므로 동일한 문제를 다시 풀 일이 없어 빠르다.
  • 그러나 피보나치 수열처럼 동일한 문제를 또 풀고 또 풀고 해야하는 방식엔 분할 정복 기법은 적합하지 않다.
    • 5 = 3 + 4, 3 = 2 + 1, 4 = 3 + 2
      • 5 를 풀 때 3 과 4 를 풀어야 5 를 풀 수 있는데 4 를 푸는 과정안에서 3 을 또 풀어야 한다. 이렇게 동일한 문제를 또 풀고 또 풀고 해야 해서 매우 비효율적이다.
  • 무려 시간 복잡도가 \(2^{N}\). 50번째 피보나치 수열을 구하려면 \(2^{50}\) 번 연산을 해야 한다는 얘기다.
    • N 만큼의 높이를 가진 트리를 두 갈래로 내려가는 짓을 해야 하므로!

int DiveAndConquer(int x)
{
    if (x == 1) return 1;
    if (x == 2) return 1;
    return DiveAndConquer(x - 1) + DiveAndConquer(x + 1);
}

DP 👉 하나의 문제는 단 한번만 풀도록 매번 저장 하는 알고리즘. 다시 그 문제를 요구 할 때는 기존에 이미 저장해 두었던 것을 가져온다. 분할 정복처럼 여러개의 하위 문제들로 나누어 먼저 처리해야 할 때 사용할 수 있다. 👉 피보나치 수열.

저장을 하여 불필요한 반복적인 계산을 줄이고, 효율적으로 최적해를 찾는다. 큰 문제를 구할 때 작은 문제들로 쪼개어 구하며, 큰 문제가 최적해를 구하는 문제라면 작은 문제들도 자기 기준에서의 최적해를 구해야 한다.

계산하여 순서대로 이를 저장해 하나의 보관용 테이블을 만든다.(다이나믹 프로그래밍의 ‘프로그래밍’이 이 테이블을 만든다는 의미에서 붙여진 것이다.) 피보나치 수열에 대입해보자면 a[0], a[1], a[2], … 차례대로 n열까지의 테이블을 채워 나감

• 동적 계획법은 또 다시 동일한 문제를 풀 일이 없도록, 처음으로 한 번 풀었을 때 그 결과를 배열 같은 곳에 저장을 해두고, 동일한 문제를 만나면 배열에서 가져오는 식으로 해결한다.
  • 즉 동일한 문제를 또 푸는데에 걸리는 시간은 소요 되지 않는다. 기존에 풀어서 저장해둔 결과를 가져오면 그만인 것이다.
  • 피보나치 수열에서 5 = 3 + 4, 3 = 2 + 1, 4 = 3 + 2
    • 3 을 구해야 하는 문제를 4 를 구하는 과정에서 미리 결과를 도출하여 저장해두었다면 5 를 구하는 과정에서 필요한 3 은 그냥 4 를 구하는 과정에서 저장했던 것을 그대로 가져오면 될 뿐이다. 3 을 구하기 위해 또 문제를 풀 필요가 없다.
  • 시간 복잡도는 무려 \(O(N)\) 으로 줄어든다.
    • 피보나치 수열을 예로 들자면 일직선으로 내려가는 트리와도 같아지기 때문이다. 동일한 문제는 이미 결과를 구해놨기 때문에 또 내려가서 구할 필요가 없어져서.

int save[100];
int DP(int x)
{
    if (x == 1) return 1;
    if (x == 2) return 1;
    if (save[x] != 0) return save[x];
    return save[x] = DP(x - 1) + DP(x + 1);
}

• DP 첫 번째 방법 👉 재귀 하되 저장
  • 처음 만난 문제가 아니면, 즉, 기존에 만나서 저장했던 문제라면 if (save[x] != 0) 기존에 풀고 저장해뒀던 것을 불러오기만 하면 된다. return save[x]
  • 처음 만난 문제라면 return save[x] = DP(x - 1) + DP(x + 1)
    • 계산 해서 구해야 됨
  • 위 부터 계산해 내려가는 Top - Down 방식.

int save[100];
int DP(int x)
{
    save[0] = 0; save[1] = 1;
    for(int i = 2; i <= n; i++)
        save[i] = save[i - 1] + save[i - 2];
    return save[x];
}

• DP 두 번째 방법 👉 재귀 안 쓰고 반복문으로 처음부터 저장해나감
  • 아래 부터 계산해 올라가는 Bottom - Up 방식.

👩🏼 동적 계획법을 사용할 수 있는 가정

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
   • 마치 피보나치 수열처럼.
   • 큰 문제들은 작은 문제들로 이루어진다. 작은 문제들로 분할이 가능.
   • 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
   • 즉, 점화식을 세울 수 있어야 한다.
   • 4 를 구하는 과정에서 구해서 저장했던 3 을, 5 를 구하는 과정에서도 그대로 쓸 수 있는 문제여야 한다. 동일하게.

👩🏼 동적 계획법 사용 예시

참고 https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

막대기 자르기

막대기 길이가 [0, 1, 2, 3, 4] 이고 각각 막대기의 가격이 [0, 1, 5, 8, 9] 일 때, 길이가 4 인 막대기를 자를 때 얻을 수 있는 최대 가격은?

• 막대기 길이가 4 일 때의 최고 가격
  • 자르지 않고 그냥 4 길이인 막대기
    • 막대기 길이가 0 일 때의 최고 가격 + 막대기4 가격
  • [1, 3] 으로 두 개로 자른 막대기
    • 막대기 길이가 1 일 때의 최고 가격 + 막대기3 가격
    • 막대기 길이가 3 일 때의 최고 가격 + 막대기1 가격
  • [2, 2] 으로 두 개로 자른 막대기
    • 막대기 길이가 2 일 때의 최고 가격 + 막대기2 가격

즉, 점화식을 세울 수 있다. Ri을 i 길이인 막대기의 최고 가격이라고 하고 Pi을 i길이인 막대기의 가격이라고 할 때 R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0) 로 점화식을 세울 수 있다. 마치 피보나치 수열 같다. 막대기 길이가 4 일 때의 최고 가격은 막대기 길이가 3 일 때의 최고 가격도 똑같이 재귀적으로 구해야 한다. 피보나치 수열 처럼.. 단, DP 방법을 사용하여 똑같은 계산은 또 하지 않도록 배열에 저장한다!

• R[1] = max(P[1] + R[0])
• R[2] = max(P[2] + R[0], P[1] + R[1])
• R[3] = max(P[3] + R[0], P[2] + R[1], P[1] + R[2])
• R[4] = max(P[4] + R[0], P[3] + R[1], P[2] + R[2], P[1] + R[3])

int dp(vector<int> P, n)
{
    vector<int> R(n);
    
    for (int i = 0; i < n; i++)
    {
        int temp = -1;
        for (int j = 0; j < i; j++)
        {
            temp = max(temp, p[i] + r[j - i]);
        }
        r[i] = temp;
    }

    return r[n];
}

**

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기