[알고리즘] LIS LCS

- LIS (Longest Increasing Subsequence)

1~N 번까지 순서대로 i번째 dp값을 최신화해준다. j는 i보다 작은 수 즉 배열의 앞에 있는 숫자라고 할 때 i번째 숫자가 j번째보다 크고 dp [i]가 dp [j] + 1보다 작다면 dp [i]의 값을 dp [j]+1로 최신화해준다.

int arr[101];
int dp[101] ;
int N,ans = 0;

void LIS() {
	for (int i = 0; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i]> arr[j]) {
				if (dp[i] < dp[j] + 1)
					dp[i] = dp[j] + 1;
			}
		}
		ans = max(ans, dp[i]);
	}
}

위의 풀이는 DP를 활용한  O(N^2)의 풀이 방법이다.

lower_bound 를 활용하여 O(NlogN)의 시간에 풀 수도 있다.

배열을 순회하면서 원소를 확인하는데 LIS의 끝에 추가 될 수 있다면 추가를 하고 그렇지 않다면 자신보다 같거나 큰 원소를 lower_bound를 활용하여 찾아내 자신과 교체한다. 이렇게 되면 LIS 배열 자체를 알 수는 없지만 LIS 배열의 길이는 알 수 있다. 배열 자체를 알고 싶으면 또 다른 배열을 하나 추가하여 자신이 몇번째 LIS 원소로 추가되었는지를 기억한다음 배열의 뒤에서 부터 역추적 한다면 LIS 배열도 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 1000010

using namespace std;

int N;
int arr[MAX],dp[MAX],memo[MAX];
stack <int> ans;
int len = 0;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	dp[len++] = arr[0];
	memo[0] = 0;
	for (int i = 1; i < N; i++) {
		if (arr[i] > dp[len - 1]) {
			dp[len++] = arr[i];
			memo[i] = len - 1;
		}
		else {
			int* iter = lower_bound(dp, dp + len, arr[i]);
			*iter = arr[i];
			memo[i] = iter - dp;
		}
	}
	cout << len << "\n";
	int cnt = len - 1;
	for (int i = N - 1; i >= 0; i--) {
		if (cnt == memo[i]) {
			ans.push(arr[i]);
			cnt--;
		}
	}
	while (!ans.empty()) {
		cout << ans.top() << " ";
		ans.pop();
	}
	return 0;	
}

- LCS (Longest Common Subsequence)

문자열 두 개가 있을 때 한 문자열의 i번째 문자와  다른 한 문자열의 j번째 문자를 비교하여

문자가 같다면 i와 j를 전 문자열들 중 LCS에서 1을 더하면 되므로 dp [i-1][j-1] + 1을 해주면 된다. 

문자가 같지 않다면 i-1과 j의 LCS와 i와 j-1의 LCS의 큰 값을 이어오면 되므로 dp [i-1][j]와 dp [i][j-1] 중 큰 값을 가져온다.

int dp[1001][1001];
int solve(string s,string t) {
	for (int i = 1; i <= s.size(); i++) {
		for (int j = 1; j <= t.size(); j++) {
			if (s[i-1] == t[j-1]) // dp[1] 이 0번째 문자열을 가리킴
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	return dp[s.size()][t.size()];
}

- LCS (Longest Common Substring)

위 Longest Common Subsequence 와의 차이는 두 문자가 같지 않을 때 1로 초기화시켜준다는 것과 답이 dp값들중 최고값이라는 것이다.

int solve(string s, string t) {
	int res = 0;
	for (int i = 1; i <= s.size(); i++) {
		for (int j = 1; j <= t.size(); j++) {
			if (s[i - 1] == t[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				res = max(res, dp[i][j]);
			}
			else
				dp[i][j] = 0;
		}
	}
	return res;
}