LCS 구하기

LCS란?

LCS는 최장 공통부분 수열(Longest Common Subsequence)이다. 이번 문제 해결기법 중간고사 5번 문제였다. 수업시간에는 DP를 생각하지 못하고 if와 절차 지향적으로 풀려고 했다. 당연히 풀지 못했다. 생각해야 할 조건이 너무 많았다. 집에 와서 알고리즘을 배워보니 간단하게 DP로 풀 수 있는 문제였다.

LCS의 최장 길이 찾는 알고리즘

1. 최장 공통 부분수열은 비교하는 두 배열을 index로 가지는 2차원 배열을 만들고 하나씩 비교해 나가는 것이다.
2. 만약 abcde와 abcfg를 비교한다고 했을 때, 2차원 배열의 행을 abcde 열을 abcfg라고 한다. 행을 기준으로 첫 번째 문자부터 다른 문자와 모두 비교해 같은지 안 같은지 검사한다.
3. 아래의 코드 처럼 같으면 그 전 문자의 비교에다가 1을 더해준다. 왜냐하면 지금 검사하는 2 문자가 같으면 전 문자 비교와 이어지기 때문이다.

//같을 때
if stringA[i] == stringB[j] {
	 LCS[i][j] = LCS[i-1][j-1] + 1; 
}

1. 만약 다르면 각 행의 전 문자와 열의 전 문자 중 큰 수를 찾는다.

//다를 때
else{
		LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
}

위 과정을 반복해 모두 검사한 뒤 가장 큰 숫자를 찾는다.

• 최종코드

## LCS란?

LCS는 최장 공통 부분수열(Longest Common Subsequence)이다. 이번 문제해결기법 중간고사 5번 문제 였다. 수업시간에는 DP를 생각하지 못하고 if와 절차지향적으로 풀려고했다. 당연히 풀지 못했다. 생각해야할 조건이 너무 많았다. 집에 와서 알고리즘을 배워보니 간단하게 DP로 풀 수 있는 문제였다. 

## LCS의 최장 길이 찾는 알고리즘

1. 최장 공통 부분수열은 비교하는 두 배열을 index로 가지는 2차원 배열을 만들고 하나씩 비교해 나가는 것이다.
2. 만약 abcde와 abcfg를 비교한다고 했을 때, 2차원 배열의 행을 abcde 열을 abcfg라고 한다. 행을 기준으로 첫번째 문자부터 다른 문자와 모두 비교해 같은지 안 같은지 검사한다.
3. 아래의 코드 처럼 같으면 그 전 문자의 비교 에다가 1을 더해준다. 왜냐하면 지금 검사하는 2문자가 같으면 전 문자 비교와 이어지기 때문이다.

```cpp
//같을 때
if stringA[i] == stringB[j] {
	 LCS[i][j] = LCS[i-1][j-1] + 1; 
}
```

1. 만약 다르면 각 행의 전 문자와 열의 전 문자 중 큰 수를 찾는다. 

```cpp
//다를 때
else{
		LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
}
```

위 과정을 반복해 모두 검사한 뒤 가장 큰 숫자를 찾는다. 

- 최종 코드
    
    ```cpp
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
    	string str1; string str2;
    	int res = 0;
    	cin >> str1 >> str2;
    	vector<vector<int>> lcs(str1.size() + 1);
    	for (int i = 0; i <= str1.size(); ++i) {
    		for (int j = 0; j <= str2.size(); ++j) {
    			lcs[i].push_back(0);
    		}
    	}
    	for (int i = 0; i < str1.size(); ++i) {
    		for (int j = 0; j < str2.size(); ++j) {
    			if (str1[i] == str2[j]) {
    				lcs[i+1][j+1] = lcs[i][j] + 1;
    				if (res < lcs[i + 1][j + 1]) res = lcs[i + 1][j + 1];
    			}
    			else {
    				lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j]);
    				if (res < lcs[i + 1][j + 1]) res = lcs[i + 1][j + 1];
    			}
    		}
    	}
    	cout << res << "\n";
    }
    ```
    

## LCS 찾기

위에 만든 2차원 배열을 이용하여 찾을 수 있다.

1. 2차원 배열의 가장 마지막 값에서 시작한다. 결과값을 저장할 result vector를 만들었다.
2. LCS[i-1][j] 와 LCS[i][j-1] 중 현재 값과 같은 값을 찾는다.
3. 같은 값이 있으면 그곳으로 이동한다.
4. 같은 값이 없으면 그 문자를 벡터에 넣고 LCS[i-1][j-1]로 이동한다.
5. 이 과정을 반복하다가 0으로 이동하게 되면 종료한다.
- 최종 코드
    
    ```cpp
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
    	string str1; string str2;
    	int res = 0;
    	cin >> str1 >> str2;
    
    	vector<vector<int>> lcs(str1.size() + 1);
    	for (int i = 0; i <= str1.size(); ++i) {
    		for (int j = 0; j <= str2.size(); ++j) {
    			lcs[i].push_back(0);
    		}
    	}
    	for (int i = 0; i < str1.size(); ++i) {
    		for (int j = 0; j < str2.size(); ++j) {
    			if (str1[i] == str2[j]) {
    				lcs[i+1][j+1] = lcs[i][j] + 1;
    				}
    			else {
    				lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j]);
    			}
    		}
    	}
    
    	vector<char> LCS;
    	int i = str1.size(); int j = str2.size();
    	while (1) {
    		if (lcs[i][j] == 0) {
    			break;
    		}
    		if (lcs[i][j] == lcs[i - 1][j]) {
    			i = i - 1; j = j;
    			continue;
    		}
    		if (lcs[i][j] == lcs[i][j-1]) {
    			i = i; j = j-1;
    			continue;
    		}
    		i = i - 1; 
    		j = j - 1;
    		LCS.push_back(str1[i]);
    	}
    
    	for (int i = LCS.size() - 1; i >= 0; --i) {
    		cout << LCS[i];
    	}
    }
    ```

LCS 찾기

위에 만든 2차원 배열을 이용하여 찾을 수 있다.

1. 2차원 배열의 가장 마지막 값에서 시작한다. 결괏값을 저장할 result vector를 만들었다.
2. LCS [i-1][j]와 LCS [i][j-1] 중 현재 값과 같은 값을 찾는다.
3. 같은 값이 있으면 그곳으로 이동한다.
4. 같은 값이 없으면 그 문자를 벡터에 넣고 LCS [i-1][j-1]로 이동한다.
5. 이 과정을 반복하다가 0으로 이동하게 되면 종료한다.

• 최종 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	string str1; string str2;
	int res = 0;
	cin >> str1 >> str2;

	vector<vector<int>> lcs(str1.size() + 1);
	for (int i = 0; i <= str1.size(); ++i) {
		for (int j = 0; j <= str2.size(); ++j) {
			lcs[i].push_back(0);
		}
	}
	for (int i = 0; i < str1.size(); ++i) {
		for (int j = 0; j < str2.size(); ++j) {
			if (str1[i] == str2[j]) {
				lcs[i+1][j+1] = lcs[i][j] + 1;
				}
			else {
				lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j]);
			}
		}
	}

	vector<char> LCS;
	int i = str1.size(); int j = str2.size();
	while (1) {
		if (lcs[i][j] == 0) {
			break;
		}
		if (lcs[i][j] == lcs[i - 1][j]) {
			i = i - 1; j = j;
			continue;
		}
		if (lcs[i][j] == lcs[i][j-1]) {
			i = i; j = j-1;
			continue;
		}
		i = i - 1; 
		j = j - 1;
		LCS.push_back(str1[i]);
	}

	for (int i = LCS.size() - 1; i >= 0; --i) {
		cout << LCS[i];
	}
}