2022-03-20::DP

Dynamic Programming

DP는 분할 정복의 한 형태이다. 분할정복 방식은 다음과 같은 형태로 진행된다. DP문제가 판별도 어렵고 그 방식이 다양하기 때문에 상당한 창의력이 요구되는 파트라고 생각한다. 특정 단계에 영향을 끼치는 단계가 무엇인지, 단계간 관계는 어떠한 형태인지 파악하는 것이 중요하다.

1. 한 번에 해결하기 힘든 문제를 잘게 자른다.
2. 잘게 자른 문제의 해답을 이용해 더 큰 문제를 해결한다.
3. 최종 답을 구한다.

DP위와 같은 형태에 중간 값들을 저장해 중복되는 계산을 생략한다는 특징이 있다. DP문제 중 가장 처음 만나는 것 중 하나가 바로 피보나찌 수열 구하기이다. 피보니찌 수열의 N번째 요소를 구할 때, 메모이제이션을 사용해 시간효율이 더 좋은 알고리즘을 만들 수 있다. DP는 이처럼 문제를 세분화한 다음 중복되는 연산의 해답을 미리 저장해놓고 꺼내쓰는 방식을 취한다. 

DP판별법

한 문제가 DP인지 아닌지 판별하는 방법은 다음과 같다.

1. 하나의 문제를 여러 문제로 나눈다.
특히 문제의 범위가 0~10인 경우, 0, 0~1, 0~2, 0~3, .., 0~10(답)과 같은 bottom-up형태로 나누는 경우가 많다.
나눈 문제를 반복적으로 해결하기 때문에 반복문이 사용된다.
2. 단계 간 관계식을 도출한다.
이전 범위의 답을 이용해 다음 범위의 문제를 해결한다. 관계식은 배열의 인덱스로 표현되기 때문에 컨테이너로 배열을 사용한다. vector와 같은 동적 컨테이너 보다는 문제에서 주어진 범위로 배열공간을 미리 할당해놓은 다음 사용하는 것이 좋다.

단계 간 관계식이 증명되는 그 문제는 DP를 이용해서 풀 수 있다.

DP문제 예시

https://www.acmicpc.net/problem/1149

1149번: RGB거리

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

int main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, in; cin>>n;
  vector<int> street[1000];
  for(int i=0; i<n; i++) {
    for(int j=0; j<3; j++) {
      cin>>in;
      street[i].push_back(in);
    }
  }

  for(int i=1; i<n; i++) {
    street[i][0] += min(street[i-1][1], street[i-1][2]);
    street[i][1] += min(street[i-1][0], street[i-1][2]);
    street[i][2] += min(street[i-1][0], street[i-1][1]);
  }

  sort(street[n-1].begin(), street[n-1].end());
  cout<<street[n-1][0];

  return 0;
}

기본적으로 답을 구하는데 영향력이 있는 데이터들을 배열로 표현한다고 생각하면 된다. 경우에 따라 1차원 또는 2차원 배열로 나타낸다. 위 문제 역시 2차원 배열로 입력값을 표현한 다음 배열 안에서의 관계식을 도출한다.

 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

int main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, in;
  cin >> n;
  vector<int> arr, dp;
  for (int i = 0; i < n; i++)
  {
    cin >> in;
    arr.push_back(in);
  }

  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    int max__ = 0;
    for (int j = i - 1; j >= 0; j--)
      if (arr[j] < arr[i])
        max__ = max(dp[j], max__);
    dp.push_back(max__+1);
    ans = max(ans, max__+1);
  }

  cout << ans;

  return 0;
}

보통 한 단계를 해결하는데 영향을 주는 요소는 많지 않지만, 위 문제의 경우에는 이전 단계의 모든 답이 현재 단계에 영향을 줄 수 있다. 때문에, 처음에 관계식을 떠올리기 어려웠다. 시간복잡도 역시 높다. O(n^2)

 

https://www.acmicpc.net/problem/9251

9251번: LCS

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>

using namespace std;

int dp[1001][1001];
int main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  string s1, s2;
  cin >> s1 >> s2;

  int n1 = s1.length();
  int n2 = s2.length();

  for (int i = 1; i <= n1; i++)
    for (int j = 1; j <= n2; j++)
      dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + (s1[i-1] == s2[j-1])});

  cout << dp[n1][n2];

  return 0;
}

이 문제의 풀이는 상당히 간소하지만, DP문제임을 판별하는 것과 관계식을 도출하는 것이 어려웠다.

 

새로 알게된 테크닉

max함수 안에 {}를 통해 배열을 넣을 수 있다.

(true)는 int 1로 사용된다. 만약(s1[i-1] == s2[j-1]) 안이 참이면 1이 된다.

이터레이터 itr의 인덱스는 itr-arr.begin()으로 표현 가능하다

아래 설정 통해 컴파일러, OS에 독립적인 자료형을 사용할 수 있다.

#include <stdint.h>
int64_t long long;