[알고리즘] Longest Common Subsequence(LCS) - 1부

Longest Common Subsequence(LCS)

동적 계획법을 사용하는 대표적인 알고리즘으로, 문자열 두 개가 주어졌을 때 처음부터 끝 순서로 문자를 뽑아서 만들 수 있는 가장 큰 부분 문자열을 구하는 알고리즘이다.

🔍 동적 계획법 사용 이유

쉽게 생각할 수 있는 가장 큰 부분 문자열을 구할 수 있는 방식 중 하나는 각 문자열에서 부분 문자열을 모두 구한 후 중복되는 부분 문자열 중 가장 큰 문자열을 찾는 방법이다. 이 때 동적 계획법을 사용하면 이전까지의 기록을 참고해서 문자열의 각 문자 하나씩을 검사해 나가기 때문에 연산의 개수가 줄어든다.

💡 Note
부분 문자열을 하나씩 모두 찾아내는 완전 탐색 (Brute Force) 방법을 사용하기 때문에 문자열의 길이가 늘어날 수록 소요되는 시간이 기하급수적으로 늘어난다.

🌌 LCS 의 원리

문자열을 배열로 나타낼 때, X[0..m-1] 과 Y[0..n-1] 을 각각 길이 m 과 n 의 문자열이라고 하자. 그리고 L(X[0..m-1], Y[0..n-1]) 가 두 문자열의 LCS의 길이를 를 나타낸다고 하자.

L(X[0..m-1], Y[0..n-1]) 를 재귀적으로 정의하면 아래와 같다:

• 만약 두 문자열의 마지막 원소가 같다면, L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0…m-2], Y[0..n-2] 이다. LCS에 마지막 원소가 포함되면서 길이에 1을 추가하기 때문이다.
• 그렇지 않다면 L(X[0..m-1], Y[0..n-1]) = MAX(L(X[0…m-1], Y[0…n-2]), L(X[0…m-2], Y[0…n-1])) 이다. 이유는 두 문자열의 LCS 는 어쨌든 마지막 원소 두개가 같은 자리에서 중복되지 않기 때문에 두 문자열 중 하나에서 마지막 문자열이 포함되더라도 다른 하나에서는 포함되지 않게 된다. 그래서 X 에서 마지막 문자를 뺀 문자열과 Y 의 LCS의 길이, 그리고 X 와 Y에서 마지막 문자를 뺀 문자열의 LCS 의 길이 중 긴 것이 결국 두 문자열의 LCS 의 길이와 같다 할 수 있다.

이렇게 LCS 를 구하는 문제도 작은 부분 문제로 쪼개어 풀 수 있다.

이를 표로 나타낼 수 있는데, 가장 기반이 되는 두 문자열 (첫 문자들, A 와 D) 부터 비교하면서, (재귀적으로 호출했을 때는 가장 기반이 되는 문자열까지 쪼개진 후 쪼개진 순서의 거꾸로 비교가 진행될 것이다)

• 같을 때는 각 문자열에서 맨 끝 문자를 뺀 문자열 두개의 LCS 의 길이 (왼쪽 대각선 위칸) 에 1을 추가해서 적고,
  
  
• 다를 때에는 A 문자열에서 끝 하나를 뺀 문자열과 B 문자열의 LCS 의 길이 (위쪽 칸) 와 A 문자열과 B 문자열에서 끝 문자 하나를 뺀 문자열의 LCS 의 길이 (왼쪽 칸) 중 큰 숫자를 적는다.
  
  
• A 문자열 DCABDC 와 B 문자열 ABCDCBA 의 LCS 를 구하는 방법
  
  

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C
  A
  B
  D
  C

  2단계

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A
  B
  D
  C

  3단계

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A	1	1	1	1	2	2	3
  B
  D
  C

  4단계

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A	1	1	1	1	2	2	3
  B	1	2	2	2	2	3	3
  D
  C

  5단계

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A	1	1	1	1	2	2	3
  B	1	2	2	2	2	3	3
  D	1	2	2	3	3	3	3
  C

  6단계

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A	1	1	1	1	2	2	3
  B	1	2	2	2	2	3	3
  D	1	2	2	3	3	3	3
  C	1	2	3	3	4	4	4

  이렇듯 표의 내용이 모두 부분 문제의 결과를 참고해서 작성되어 완성된다.
  
  완성 후에는 두 문자열의 부분 문자열들의 LCS 의 길이가 변경이 있을 때를 보고 두 문자열의 LCS 를 구할 수 있다. 변경이 일어났다는 것은 끝 문자가 일치해서 새로운 LCS의 길이가 1 늘어났다는 의미이기 때문이다. 물론 가장 긴 부분 문자열을 찾는 것이기 때문에 변동이 일어난 숫자들 중 가장 큰 숫자를 기준으로 왼쪽으로 가면서 변동 시점들을 확인하면 된다. 아래 표에 확인해야 할 부분들을 이모지를 활용해서 표시했다.
  
  

  	A	B	C	D	C	B	A
  D	0	0	0	1	1	1	1
  C	0	0	1	1	2	2	2
  A	1✅	1	1	1	2	2	3
  B	1	2✅	2	2	2	3	3
  D	1	2	2	3✅	3	3	3
  C	1	2	3	3	4✅	4	4

  그래서 두 문자열의 LCS 는 ABDC 가 되는 것이다.

📢 LCS 의 시간 복잡도

시간복잡도는 문자열 A의 길이 * 문자열 B의 길이 이기 때문에 O(N^2) 이다.

 

다음 포스트에서는 LCS 를 코드로 구현해보겠다.