[알고리즘] 백준 9251번: LCS (C++), 최장 공통 부분 '수열'

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

9251번: LCS

 

우선, 글에 들어가기 앞서 포스팅의 제목에서 '수열'이라고 강조한 이유는 '문자열'과 '수열'은 다른 의미이기 때문이다.

저번에 LIS를 포스팅하면서는 수열과 집합의 차이를 느꼈는데 이번 키워드에서는 문자열과 수열의 차이를 알아야 한다.

(집합에 관해 적은 포스팅: https://draw-code-boy.tistory.com/85)

 

[문자열 vs 수열]

"HELLO"라는 문자열이 있다고 하자.

여기서 부분 문자열(Substring)과 부분 수열(Subsequence)을 구한다고 하면

부분 문자열로는

"HE", "ELLO" 등 여러 부분 문자열을 구할 수 있고,

부분 수열로는 

"HE", "ELLO", "HLO", "EO"등 여러 부분 수열을 구할 수 있다.

 

여기서 알 수 있는 건 '부분 문자열이 부분 수열에 속한다.'

부분 문자열의 특성으로는 연속적이어야 함을 알 수 있다.

부분 수열은 이를 포괄하여 순서를 가지면 되고, 부분 집합은 부분 수열까지 포괄한다.

 

'부분 문자열 ⊂ 부분 수열 ⊂ 부분 집합'

 

---

[솔루션: 백트래킹, 시간 초과]

DP 솔루션을 무시한 채로 내 힘으로 풀어보려 했었다.

떠올랐던 방법이 백트래킹을 사용해서 부분 수열을 구하고, 이를 하나하나 비교하기에는 시간이 꽤 많이 걸릴 듯했다.

 

문자열 하나에서 백트래킹을 통해 나올 수 있는 부분 문자열을 구하는 시간 복잡도:

어떠 한 문자를 선택할지 선택하지 않을지: 2번의 연산

문자열의 길이: n

>> O(2^n)

다른 문자열도 마찬가지로 길이가 m이라고 했을 때,

>> 총 O(2^n * 2^m)

 

두 문자열의 길이로 올 수 있는 최댓값이 1000 임을 고려하면 O(2^2000)으로 시간 초과를 유발한다.

---

[솔루션]

(+참고: http://melonicedlatte.com/algorithm/2018/03/15/181550.html)

이곳에서 설명을 엄청 잘해두셨다. 2차원 배열을 행렬 표 그려두신 것을 보고, 이해가 빠르게 됐다.

LCS 알고리즘에서도 2차원 배열이 사용되었다. 최근 들어 2차원 배열의 응용력이 중요하다는 게 다시 한번 체감된다.

 

[방법]

1) 2중 for문을 통해 두 문자열에서 각각 한 문자를 비교한다.

2) 0행과 0열은 비워져있어야 한다.

3-1) 문자가 같을 때, cache[i][j] = cache[i - 1][j - 1] + 1;

3-2) 문자가 다를 때, cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);

 

단순히 방법에 대한 글만 보았을 때는 이해가 가지 않는다. 참고했던 포스팅처럼 행렬 표를 보면 쉽게 이해가 가능하다.

(2번 방법에 맞게 0행과 0 열도 따지며 그들은 비워져있어야 한다.)

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

3번 방법의 점화식을 이해하기 위해 두 가지 경우를 살펴보자.

 

1) 문자가 같을 때, cache[i][j] = cache[i - 1][j - 1] + 1;

파란색 배경의 행렬 표 숫자를 보면 "ACAYKP"와 "CAP"를 비교했을 때 공통부분 수열의 길이가 3이 나온다는 의미다.

이때의 공통부분 수열은 "ACAYKP", "CAP" => "CAP"

 

그렇다면 왜 저 점화식이 통하는가?

간단하게 이해하는 방법은 cache[i - 1][j - 1] 일 때의 공통부분 수열을 보면 된다.

"ACAYK"와 "CA"로 공통 부분 수열은 "CA"가 된다.

여기서 각자 다음 문자(둘 다 'P')를 추가했더니 같았다.

>> 즉, '공통부분 수열의 길이가 더 늘어난다.'와 같은 말이 된다.

>>>> 여기서 DP의 메모이제이션을 사용하여 그 전 수열의 길이까지 기억된 값에 +1을 해주는 것이다.

 

2) 문자가 다를 때, cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);

노란색 배경의 행렬 표 숫자를 보면 "ACA"와 "CAP"를 비교했을 때 공통부분 수열의 길이가 2가 나온다는 의미다.

이때의 공통부분 수열은 "ACA", "CAP" => "CA"

 

그렇다면 왜 저 점화식이 통하는가?

cache[i - 1][j] 일 때와 cache[i][j - 1] 일 때를 각각 보면

cache[i - 1][j]일 때는 "ACA"와 "CA"를 비교하고 있다. 이때의 수열의 길이는 2.

cache[i][j - 1]일 때는 "AC"와 "CAP"를 비교하고 있다. 이때의 수열의 길이는 1.

>> 추가하는 문자가 다르기 때문에 위 두 가지 경우에서 문자를 추가한다 해도 수열의 길이가 늘어날 수가 없다.

>> 즉, "AC"와 "CA"라는 문자열에서 각각 한 문자를 더했을 때 최장 공통부분 수열의 길이는 두 문자열에 한 문자를 넣은 경우 중 더 큰 값과 같다는 말이 된다.

>>>> 간단하게 말하면 '두 문자열에서 추가하는 문자가 다르기 때문에 가능하다'가 적합한 거 같다.

---

[AC 코드]

문자열의 처음부터 읽으면 바로 문자열 0행 0열을 포함한다는 조건을 못 가지기 때문에 입력을 받고, 앞에 ' '를 추가해주었다.

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

int cache[1001][1001];

int main() {
	string a, b;
	cin >> a >> b;
	a = ' ' + a;
	b = ' ' + b;

	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (a[j] == b[i]) {
				cache[i][j] = cache[i - 1][j - 1] + 1;
			}
			else {
				cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
			}
		}
	}

	/*
	for (int i = 0; i < b.size(); i++) {
		for (int j = 0; j < a.size(); j++) {
			cout << cache[i][j] << ' ';
		}
		cout << '\n';
	}
	*/

	cout << cache[b.size() - 1][a.size() - 1];
	return 0;
}