[이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

 🤔 최장 공통 부분 수열 (LCS, Longest Common Subsequence)이란?

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 최장 공통 문자열(Longest Common Substring)과 달리 연속적인 문자열이 아니어도 된다. 비슷한 용어이지만 연속성에서 차이를 보이므로 주의할 것!

 

예를 들어보자. 두 문자열 "ASDFASDF", "ASFASDF"에서,
Longest Common Substring은 연속하는 문자열이므로 "ASDFASDF", "ASFASDF"로 "FASDF"가 되지만,
Longest Common Subsequence는 연속하지 않아도 되므로 "ASDFASDF", "ASFASDF"로 "ASFASDF"가 된다.

 

최장 공통 부분 수열(이하 LCS)은 여러 개가 있을 수 있으며, LCS의 길이를 구하는 문제는 동적계획법(DP, Dynamic Programming)을 사용하면 해결할 수 있다. LCS를 구하는 문제의 경우에는 DP를 통해 LCS의 길이를 먼저 구하고, DP 결과를 역추적하여 해결할 수 있다.

 

시간복잡도는 두 문자열의 길이(m, n)에 비례하여 $O(m \times n)$이다.

---

 📌 풀이 방법

 1. LCS의 길이

• 동적 프로그래밍(DP)을 활용하여 해결한다. 풀이 방법은 다음과 같다.
• 두 문자열 str1, str2의 길이를 각각 m, n이라고 할 때, dp[m+1][n+1]인 2차원 배열을 사용한다. dp[m][n]은 str1의 m번째 문자, str2의 n번째 문자까지 고려했을 때 공통 부분 수열의 최대 길이이다.
• str1[m] == str2[n]인 경우, 공통 문자로 저장되므로 저장된 LCS 길이에 1을 더하여 저장한다.
• str1[m] != str2[n]인 경우, 공통 문자가 아니므로 이전 값 중 더 큰 값을 저장한다. "str1의 m-1번째 문자, str2의 n번째 문자까지 고려한 값" (dp 표에서 위에 있는 값)과 "str1의 m번째 문자, str2의 n-1번째 문자까지 고려한 값" (dp 표에서 왼쪽에 있는 값) 중 더 큰 값을 선택한다.
• 실제로 str1의 m번째 문자는 str1[m]이 아닌 str1[m-1]으로 표현하므로, str1[m-1]과 str2[n-1]을 비교한 결과를 dp[m][n]에 저장한다.
  ex) 첫 번째 문자는 str[1]이 아닌 str[0]이다.

 

배열을 보며 다시 이해해보자. 두 문자열은 str1은 "ACAYKP", str2는 "CAPCAK"라고 한다. 즉, m=6, n=6이다.

• dp[0][n]과 dp[m][0]은 모두 0으로 초기화한다. 빈 문자열과 비교했을 때는 공통 부분이 없으므로 LCS의 길이도 0이기 때문이다.

 

 

• str1[0]인 'A'와 str2의 각 문자열을 순서대로 비교한다.

두 문자가 같은 경우, 왼쪽 대각선 위에 있는 값에 1을 더한 값으로 저장한다.
dp[m][n] = dp[m-1][n-1] + 1

 

두 문자가 다른 경우, 왼쪽 값과 위쪽 값 중 더 큰 값을 적용한다.
dp[m][n] = max(dp[m-1][n], dp[m][n-1])

 

• 같은 방법으로 dp를 모두 채웠을 때, 가장 마지막에 있는 값이 LCS의 길이이다.

 

 

 2. LCS

• 위에서 구한 DP 결과인 2차원 배열을 역추적하여 구한다.
• 두 문자가 다른 경우, 가장 끝 값인 dp[m][n]에서 출발하여 왼쪽 값과 위쪽 값 중 더 큰 값을 따라 이동한다.

LCS = ""

 

• 두 문자가 같은 경우, 왼쪽 대각선 위의 값으로 이동하고, LCS에 그 문자를 저장한다.

LCS = "K"

 

• 같은 방법을 반복하여 LCS를 구한다. m과 n이 모두 0이 되면 종료하며, LCS에 문자를 추가할 때는 맨 앞에 추가한다.

LCS = "ACAK"

 

---

 ✍🏻 관련 문제

 ❓ 문제

(LCS 길이 구하는 문제)

백준 9251번: LCS https://www.acmicpc.net/problem/9251
백준 11056번: 두 부분 문자열 https://www.acmicpc.net/problem/11056
백준 1958번: LCS 3 https://www.acmicpc.net/problem/1958

 

(LCS 구하는 문제)

백준 9252번: LCS 2 https://www.acmicpc.net/problem/9252
백준 17218번: 비밀번호 만들기 https://www.acmicpc.net/problem/17218

 

(LCSubstring)

백준 5582번: 공통 부분 문자열 https://www.acmicpc.net/problem/5582

 

 💡문제풀이

[BOJ C++] 백준 9251번: LCS
[BOJ C++] 백준 11056번: 두 부분 문자열
[BOJ C++] 백준 1958번: LCS 3

[BOJ C++] 백준 9252번: LCS 2
[BOJ C++] 백준 17218번: 비밀번호 만들기

[BOJ C++] 백준 5582번: 공통 부분 문자열