LIS - lower_bound 로 푸는 이유?(다이나믹 프로그래밍)
LIS를 lower_bound로 해결하는 가장 효율적인 알고리즘이 있음에도 불구하고, 이 알고리즘을 쓰게 된 이유를 알지 못하는 사람들이 많다.
그저 효율적이라는 이유만으로 이 알고리즘을 사용한다면, 그 배경을 알지 못해 응용도 할 수 없을 뿐더러 사용할 때마다 가슴이 답답함을 느끼게 될 것이다.. (나는 이런 걸 왜 생각하지 못할까.. .)
그래서 이 알고리즘이 등장하게 된 배경에 대해서 설명해보려고 한다. (답답해서 공부했다.)
먼저 동적 프로그래밍으로 알고리즘을 설계하는 방법에 대한 것이다.
* 동적 프로그래밍 : 앞으로 푸는 문제에 대해 이전의 데이터를 활용할 수 있다면 cache에 저장하여 사용한다.
푸는 방법: https://ebang.tistory.com/89
동적 프로그래밍을 짜기 위해 수행할 과정은 다음과 같다: (매번 이렇게 하지는 않으나 이렇게 생각해보면 도움이 된다 )
1. 재귀적으로 완전 탐색을 이용해서 최적 해를 구하는 방법을 구한다.
2. 제거할 수 있는 인자 등을 파악하여 메모이제이션에 활용할 수 있는 부분을 활용한다.
다음으로 최대 증가 부분 수열 문제에 바로 들어가보도록 하자.
최대 증가 부분 수열(LIS) :
정수 S의 부분 수열이란 S에서 0개 이상의 숫자를 지우고 남은 수열을 말한다.
부분 수열을 이루는 숫자들이 순 증가(앞의 것이 항상 더 작을 때, strictly increasing )하면 이 부분 수열을 증가 부분 수열이라고 부른다.
주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제를 풀어보도록 하자.
이 문제를 최대 증가 부분수열(LIS, Longest Increasing Subsequence)찾기 문제라고 부르며,
이는 매우 유명한 동적 계획법 연습 문제 중 하나이다.
위에서 설명한 방법대로 문제를 풀어보도록 하자.
1. 재귀적으로 완전 탐색을 이용해서 최적 해를 구하는 방법을 구한다.
먼저 최대 증가 부분 수열을 찾는 문제를 숫자 하나씩으로 조각낸 뒤, 한 조각에서 숫자 하나씩을 선택하는
완전 탐색 알고리즘을 만들어보자.
수열 A를 입력받아 LIS 의 길이를 반환하는 재귀함수 (lis(A))는 A의 모든 증가 부분 수열을 만든 뒤 그 중 가장 긴 것의 길이를 반환한다 .
한 조각마다 숫자 하나를 선택하기로 했으니 lis(A)는 수열의 첫번째 숫자를 고르고 나머지 부분을 재귀적으로 만들 것이다.
이 알고리즘은 lis(A)가 첫 숫자로 A[j]를 골랐을 떄,
A[j+1, ...] 부분 수열에서 A[j]보다 큰 숫자들만 고른 부분 수열 B를 만들고 B의 lis를 재귀 호출로 계산한다.
B에서 얻은 LIS를 A[j] 뒤에 붙이면 A[j]로 시작하는 LIS를 얻을 수 있다. B의 LIS를 구할 때 A[j]나 그 이전에 선택한 숫자들을 알 필요가 없다. 이것은 이 문제에도 최적 부분 구조가 성립함을 보여준다.
이 완전 탐색 알고리즘을 실제 구현한 것이 아래와 같다.
int lis(const vector<int>& A){
//base case: 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;
}
2. 제거할 수 있는 인자 등을 파악하여 메모이제이션에 활용할 수 있는 부분을 활용한다.
이 코드는 메모이제이션을 적용하기가 까다롭다.
입력이 정수가 아니라 배열이기 때문이다.
A를 더 간단하게 표현하는 방법을 생각해보자.
여기서 A는 다음 두 가지 중 하나가 된다.
1. 원래 주어진 수열 S
2. 원래 주어진 수열의 원소 S[i]에 대해 S[i+1, ...] 부분 수열에서 S[i]보다 큰 수들만을 포함하는 부분 수열
A는 i번째 원소에 대해 그 이후의 문자열들의 부분 수열이다. 이때 부분 문제를 다음과 같이 정의해볼 수 있다.
lis[start] = S[start]에서 시작하는 부분 증가 수열 중 최대의 길이
이렇게 정의한다면 S[start]보다 뒤에 있고 큰 수들 중 하나를 다음 숫자로 결정한 뒤, 여기서 시작하는 부분 증가 수열의 최대치를 구하면 된다.
뒤의 있는 수가 모두 작아서 반복문을 수행하지 못하면 ret = 1 이 되고 반환되어 개수는 1개로 반환된다.
메모이제이션까지 구현한 다이나믹 프로그래밍은 다음과 같다.
int n;
int cache[100], S[100];
//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다 .
int lis(int start)
{
int &ret = cache[start];
if(ret != -1) return ret; //메모이제이션
ret = 1;
for(int next = start + 1; next < n; next++)
if(S[start] < S[next])
ret = max(ret, lis(next) + 1);
return ret;
}이 재귀함수를 i = 0에서 A.size()-1 까지 수행하도록 해서, 항상 증가 부분 수열의 시작 위치를 지정해서 호출하도록 한다.
for(int i = 0;i < A.size() ; i++)
ret = max(ret, lis(i));시간 복잡도
이렇게 짜면 총 O(n)개의 부분문제를 갖고, 하나를 해결할 때마다 O(n)시간의 반복문을 순회하므로
전체 O(n^2)의 시간 복잡도를 갖게 된다.
3. 더 빠른 방법
이 알고리즘은 사실 가장 빠른 방법이 야니다.
O(nlgn)에 LIS를 찾을 수 있는 알고리즘이 있기 때문이다. (설명하려는 바로 그것!)
LIS는 직관적으로 보아도 부분 수열의 가장 마지막 숫자가 가장 작은 것이 부분 수열로써 가장 이득을 볼 수 있는 구조이다. 하지만 그 위치가 중요해서 문제가 된다. 가장 작은 수들로 이루어져있어도 마지막에 위치해있다면 더 추가할 수 없어서 문제가 될 것이다.
이때, 만들 수 있는 문자열의 길이를 기준으로 하여 다이나믹 프로그래밍을 할 수 있다.
텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지를 추적한다고 해보자.
예를 들어 S의 첫 다섯 원소가 {5, 6, 7, ,1, 2}라고 하자.
이 부분 수열의 LIS는 길이가 3인 {5,6,7} 하나 밖에 없다.
반면 길이가 2인 부분 증가 수열은 {5,6}, {5,7}, {1,2}의 세 개가 있을 수 있다.
이 중 가장 유리한 것은 {1,2}이다. 다음 수로 3이나 4가 주어질 때 연결 할 수 있는 유일한 집합이기 때문이다.
원소를 추가하는 과정에서 다음과 같은 배열을 유지해보자.
C[i] = 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막 값.
이 값을 이용하도록 코드를 개선하면 LIS의 길이 k에 대해서 O(nk)의 시간에 LIS를 찾을 수 있다.
여기서 한발짝 더 나아가 C[] 가 항상 순증가한다는 사실을 이용해서
C[]에서 이분 검색을 함으로써 LIS를 O(nlgk) <= O(nlgn) 에 찾는 알고리즘을 만들 수 있다.
lower_bound는 주어진 수열 중에서 주어진 값과 같은 값을, 없다면 그보다 더 큰 값 중 가장 작은 값의 위치를 반환하고,
upper_bound는 주어진 수열 중에서 주어진 값보다 큰 값 중에서 작은 값의 위치를 반환한다.
즉 최장 증가 배열에 추가해나가면서 배열을 만들되, 검사하는 숫자를 lower_bound로 수열에서 위치를 찾았을 때, 중간 위치라면 길이 변화 없이 해당 값을 변경하고 마지막에 추가되면 그대로 가면서 길이를 찾아나갈 수 있다.
-> 각 위치에서 부분 수열이 될 수 있는 가장 작은 숫자를 담고 있는 것이다. (부분 수열 자체가 아니라!)
그래서 lower_bound를 사용하여 LIS의 길이를 빠르게 찾을 수 있는 것이다!
다음에 기회가 된다면, 이 방법으로는 LIS의 수열 자체는 저장하기가 어려우므로 해당 문제점을 어떻게 해결할지 포스팅하도록 하겠다.
*참고 : 알고리즘 문제 해결 전략(구종만)