[dynamic programming] 최대 증가 부분 수열

정상협·2021년 3월 8일

알고리즘 공부

목록 보기

2/7

지난 포스팅에서 삼각형에서의 최대 경로를 구하였다. 여기서 dp 에서 메모이제이션을 적용하는 법과 불필요한 입력을 걸러내는 최적 부분 구조에 대해 알아보았다. 여기서 좀 더 나아가 메모이제이션을 적용하는 다양한 법을 배운다.

최적화 문제 동적 게획법

모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘 설계

전체 답의 점수를 반환하는 것이 아니라, 부분 문제 중 해당하는 점수만을 반환하도록 문제 정의

재귀호출의 입력에 이전 선택에 관련된 정보가 있다면 필요한 것만 남고 줄인다.
최적 부분 구조가 성립할 경우 이전 선택에 관한 정보를 완전히 없앨 수도 있다.

입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션 한다.

메모이제이션 적용

문제

주어진 정수 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제다.
이를 최대 증가 부분 수열(LIS, Longest Increasing Sub-sequence) 찾기 문제라 한다.

ex) 1, 3, 4, 2, 4 에서는 증가 부분 수열이 1, 2, 4 로 답이 3이 된다.

해결법

1. 완전탐색에서 시작하기

/*
차례대로 조합하여 숫자의 수열이 최대보다 크면 ret값을 바꾼다.
*/
int lis(const vector<int> &A)
{
  if (A.empty())
    return 0;
  int ret = 0;
  for (int i = 0; i < A.size(); i++) 
  {
    vector<int> B;
    for (int j = i + 1; j < A.size(); j++)
      if (A[i] < A[j])
        B.push_back(A[j]);
    ret = max(ret, 1 + lis(B));
  }
  return ret;
}

vector 형태의 입력을 받고서 최대 증가 수열을 호출한다.
그러나 여기서 문제점은 입력을 vector로 받기 때문에 메모이제이션을 적용하기 까다로워진다.
물론 STL의 map을 이용할 수도 있지만 속도가 느리다.

2. 부분 문제 중 해당하는 점수만을 반환하도록 문제 정의

원래 주어진 수열 S

원래 주어신 수열의 S[i]에 대해, 부분수열에서 S[i] 보다 큰 수들만을 포함하는 부분 수열

예를 들어 3을 골랐으면 1, 2는 보지 않고 큰수들만을 포함하는 부분 수열만 있으면 된다는 것이다.

3. 필요한 것만 남고 줄이기.

필요한건 주어진 값과 비교할 마지막 값이다. 그 이전의 값들은 필요없기 때문에 버려도 된다.

4. 입력이 배열이거나 문자열인 경우

vector로 주어진 값을 적절한 변환을 통해 바꾼다.

5. 메모이제이션 적용

...
int n;
int cache[501], S[501], C[501];

int lis2(int start)
{
  int &ret = cache[start];
  if (ret != -1)
    return ret;
  //항상 S[start]는 있기 때문에 길이는 최하 1
  ret = 1;
  for (int next = start + 1; next < n; next++)
    if (S[start] < S[next])
      ret = max(ret, 1 + lis2(next));
  return ret;
}

int main(){
  ...
  int maxLen = 0;
  for (int i = 0; i < n; i++)
  {
    maxLen = max(maxLen, lis2(i));
  }
  cout << maxLen << "   LIS2" << endl;
  ...
}

지금까지 어떤 경로를 도달했는지 상관없이 남은 부분 문제는 항상 최적으로 풀어도 상관없는
최적부분구조를 만족하기 때문에 최댓값만 호출한다. 이 코드는 O(n)개의 부분 문제를 갖고, 하나를 해결 할 때 마다 O(n)시간의 반복문을 순회하므로 전체적으로 O(n^2)이다.