최장 공통 부분 수열 (Longest Common Subsequence, LCS)

1. LCS(Longest Common Subsequence) 란? 

LCS를 이해하기 위해서 먼저 '부분 문자열(Substring)'과 '부분 수열(Subsequence)'의 차이를 알아야 합니다. 

 

- 원본 : ABCDE

부분 문자열 (Substring)	원본에서 연속된 부분을 잘라낸 것	연속성 필수	BC, ABC, DE
부분 수열 (Subsequence)	원본에서 0개 이상 문자를 삭제하여 남긴 것	순서 유지 필수	ACE, BCE, AE

LCS 목표 : 두 개의 문자열 s1과 s2에서 공통으로 존재하는 부분 수열 중 가장 긴 것의 길이를 찾는 것입니다.

(부분 문자열은 부분 수열에 포함될 수 있지만, 그 반대는 성립하지 않습니다)

 

- 부분 문자열 javascript에 있는 includes와 정규식 패턴으로 추출가능 (정규식 패턴 : /{문자열}/ )

 

🤔 부분 수열도 정규식으로 가능은 하지 않을까? 

이론적으로 가능하지만, 실제 문제를 풀기에는 비효율적이고, 불가능하다고 합니다. 

 

 

A. 정규식으로 부분 수열을 표현하는 방법(비효율성)

문자열에 부분 수열 방식으로 ACE를 추출하는 방법

/A .* C .* E/

 

1) A : 첫번째 문자 'A'가 나온다. 

2) .* : 그 뒤에 어떤 문자(0개이상)가 나와도 상관 없다. (= 건너뛰기)

3) C : 'A' 다음 순서로 'C'가 나온다. 

4) .* : 다시 어떤 문자가 나와도 상관없다.
5) E : 마지막으로 'E'가 나온다. 

 

해당 방식의 문제점)

1. 정규식은 길이를 찾을수는 없고, 존재여부만 확인이 가능하다

2. 정규식으로 걸러야 하는 모든 조합 케이스를 생성해야 한다. 

3. 정규식은 가장 먼저 일치하는 패턴을 찾을 뿐 그 해답이 전체에서 가장 긴 LCS인지 보장해주지 못한다.

 

그래서, LCS 문제를 풀때는 DP로 풀어야 합니다. 

 

 

2. 왜 LCS는 DP(동적 계획법)로 풀어야 하는가? 

가능한 모든 부분 수열 조합을 암묵적으로 탐색하면서, 최적의 길이를 테이블에 기록하기 때문입니다. 

Greedy 알고리즘도 안됨! => 정규식으로 해당 케이스를 먼저 찾는거 하고 다를 바가 없음. 

 

 

 

3. LCS 점화식

복잡해 보이지만, 사실 일상생활에서 내리는 선택의 순간을 그대로 수학적으로 옮겨 놓은 것에 불과 합니다. 

 

1) 문자가 서로 같을 때 (성공의 순간!)

이 문자는 무조건 LCS에 포함시키는 것이 가장 이득입니다. (대각선)

DP[i][j] = DP[i-1][j-1] + 1

즉, 이전의 성공적인 결과에 +1을 계승하는 구조입니다.

 

 

2) 문자가 서로 다를 때 (선택의 순간!)

LCS에 들어갈 수 없기 때문에, 둘 중 하나를 버려야 합니다. (왼쪽이나 위쪽)

DP[i][j] = Math.max(DP[i-1][j], DP[i][j-1])

s1 이나 s2에서 각각 i-1, j-1까지 사용해서 둘 중 더 큰 쪽의 값을 복사하는 구조 입니다. 

 

 

 

 

[추가 스터디 자료]

https://www.youtube.com/watch?v=EAXDUxVYquY