[알고리즘] 최장 공통 부분 문자열(LCS, Longest Common Subsequence)

최장 공통 부분 문자열(LCS)

개념

공통 부분 문자열 중 가장 길이가 긴 문자열

SubString 과 SubSequence의 차이점을 알아야함

• SubString : 전체 문자열에서 연속된 부분 문자열
  • ex) ABCDEFGHI 에서 Substring은 ABC, DEFG, ABCDEF, GHI, … 등
• SubSequence : 전체 문자열에서 꼭 연속된 문자열인 것은 아닌 부분 문자열
  • ex) ABCDEFGHI 에서 Subsequence 는 ABD, AEFGH, AFI, … 등
    • 단, 앞에서부터가 아니라 순서가 뒤바뀐 IHE, BIDEHF 와 같은 문자열은 부분 문자열이 될 수 없음

LCS 는 서로 다른 문자열 중에서 공통 SubSequence를 찾는데, 그 중 길이가 가장 긴 SubSequence 를 찾으려 하는 것

• ex) ABCDEF 와 ACDGHI 와의 공통 Subsequence 중 가장 길이가 긴 것
  • ABCDEF / AZGCDGHI 에서 ACD

LCS 알고리즘 수행

문자열 RBKBGRBG 과, 문자열 BGKRBRKB 가 있다고 가정

이들을 아래와 같은 표로 나타낼 수 있음(첫번째 문자열 RBKBGRBG → 열에 표현)

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0

편의상 맨 앞의 열과 맨 첫번째 행은 0

두 번째 문자열 BGKRBRKB 를 앞에서부터 한 글자씩 가져와서 비교(행에 표현)

B를 먼저 다음 행에 가져옴

그리고 첫 번째 RBKBGRBG 문자열 하나하나와 이 B를 비교함

표에 들어가는 값은, LCS 길이의 값이 됨

1. R과 B는 서로 다름

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0

1. B와 B를 비교했더니 동일함

• 이것은 첫 번째 문자열의 {RB}와, 두 번째 문자열의 {B}를 비교한 것
• Subsequecne {RB}와 Subsequence {B}의 공통 부분은 B 이므로 그 길이인 1이 들어간 것

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1

1. B와 K를 비교했더니 서로 다름 -> {RBK}와 {B}는 여전히 공통부분이 {B}로 그 길이가 1임

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1

1. B와 B -> 동일

• 이것은 {RBKB}와 {B}를 비교한 것
• 이 둘의 공통 부분은 {B} 이므로 그 길이인 1이 들어감

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	0	1

4-1. 이렇게 채워나가서 처음 {B}와의 비교를 모두 완성해 보면 다음과 같음

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1

표를 채울 때 세 번째 행의 뒷부분부터 모두 1이 들어가게 되는 것을 알고리즘 차원에서 살펴본다면,

• 맨 처음 {RB}와 {B}를 비교하여 1이 들어갔고, 그 다음 {RBK}와 {B}를 비교할 때 이것의 공통은 여전히 {B}로 그 길이가 1 임
• 이 1이라는 값은 {RBK}와 {B}를 비교해서 얻은 1이기도 하지만, 엄밀히 말하자면 이전에 {RB}와 {B}를 비교했을 때 얻었던 1 인 것임
• 즉, 이전의 값을 확인하여 사용하게 되므로 DP 관점에서 문제를 풀 수 있음
• 이제 다음 행에 BGKRBRKB 의 G를 추가

1. R과 G -> 다름 (즉, {R}과 {BG}의 비교)

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0

1. B와 G -> 다름. 여기는 {RB}와 {BG}를 비교하는 것이므로 공통부분이 {B}로 그 길이는 1입니다.

따라서 표에는 1이 들어갑니다.

이것을 알고리즘 차원에서 살펴본다면,

• 비교했을 때 달랐을 경우, 왼쪽의 값과 위쪽의 값 중 더 큰 값을 현재 위치에 씀
• 즉, {R}과 {BG}와 비교했을 때의 LCS 길이인 0과, {RB}와 {B}를 비교했을 때의 LCS 길이인 1 중 더 큰 값인 1을 현재 칸에 쓰는 것
• 다시 말해, 지금 비교한 값은 다르므로 직전의 값으로 갱신하는데, 더 큰 전의 값을 가져오는 것

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0	1

1. K와 G -> 다름. {RBK}와 {BG}와의 비교이므로 공통 부분이 {B}로 그 길이는 1

• 이 1은 직전의 {RB}와 {BG}를 비교했을 때의 값과, {RBK}와 {B}를 비교했을 때의 값 중 더 큰 값을 가져온 것(여기서는 둘 다 1로 같았음)
• 즉, 달랐을 때는 현재 위치를 기준으로 왼쪽의 값과, 위쪽의 값 중 더 큰 값을 가져옴
• 위의 사항을 꼭 기억해 두시고, 계속 살펴보겠습니다.

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0	1	1

1. G와 B -> 다름. {RBKB}와 {BG}와의 비교이므로 공통부분이 {B}로 그 길이는 1

• 달랐을 때는 현재 위치를 기준으로 왼쪽의 값과, 위쪽의 값 중 더 큰 값을 가져옴

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0	1	1	1

1. G와 G -> 동일. {RBKBG}와 {BG}와의 비교. 공통 부분의 길이는 2

• 이것은 {RBKB} 와 {B} 를 비교했을 때의 값보다 1이 증가한 의미가 됨.
• {RBKB}에서 {RBKBG}로, {B}에서 {BG}로 되어 두 값을 비교했더니 동일한 값 G가 나왔기에, 직전의 값({RBKB}, {B}와 비교한 값)에서 1을 증가시켜 주는 것
  
• 이 직전의 값은 현재 위치를 기준으로 ‘대각선 왼쪽’ 값이 됨

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0	1	1	1	2

1. {RB}와 {BGK}를 비교. B와 K로 다름

• {RB}와, {BGK}가 되기 전 {BG}와 비교했을 때 공통이 {B}로 길이가 1 이었으므로 그 값을 가져옵니다.
• 즉, 현재 위치에서 위쪽의 값을 가져온 것임
• 이 값은 {RB}와 {BGK}를 비교해 얻은 값이기도 하지만, 엄밀히 말하자면 이전의 {RB}와 {BG}를 비교해 얻은 값이고, 이 값은 현재 위치 기준 위쪽에 해당
• 현재 위치 기준 왼쪽의 값은 {R}과 {BGK}와의 비교인데 이 때는 공통 부분이 없었음
• 따라서 달랐을 때는, 현재 위치 기준으로 왼쪽과 위쪽 중 더 큰 값을 가져온다는 것임
  • 4-1 을 확인해 보면, 이 때에는 달랐을 때, 현재 위치 기준 왼쪽 값을 가져왔었음

	0	R	B	K	B	G	R	B	G
0	0	0	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1	1	1
G	0	0	1	1	1	2	2	2	2
K	0	0	1

• 이를 모두 총정리하면 다음과 같은 규칙을 얻을 수 있음

---

규칙

• 문자열을 비교하여 같았을 때
  • 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값 + 1
• 문자열을 비교하여 달랐을 때
  • 현재 칸에 들어갈 값은 왼쪽과 위쪽의 값 중 더 큰 값

구현

• 예시코드

  for (int i = 1; i <= lenA; i++) {
              for (int j = 1; j <= lenB; j++) {
                  if (a.charAt(i-1) == b.charAt(j-1)) {
                      dp[i][j] = dp[i-1][j-1] + 1;
                  } else {
                      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                  }
              }
          }