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

LCS 알고리즘이란?

LCS는 Longest Common Subsequence 의 줄임말로, 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다.

LCS 알고리즘은 이러한 문자열을 찾는 알고리즘입니다.

이 때, Substring과 Subsequence와의 차이점을 알 필요가 있습니다.

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

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

• [예] ABCDEF 와 ACDGHI 와의 공통 Subsequence 중 가장 길이가 긴 것은
  • ABCDEF / AZGCDGHI 에서 ACD 이다.

LCS 알고리즘은 DP(Dynamic Programming)이다

그러면 위처럼 LCS를 찾는 알고리즘은 어떤 방식으로 진행될까요?

문자열 RBKBGRBG 과, 문자열 BGKRBRKB 가 있다고 해 봅시다.

이들을 아래와 같은 표로 나타낼 수 있습니다.

편의상 맨 앞의 열과 맨 첫번째 행은 0으로 둡니다.

이제, 두 번째 문자열 BGKRBRKB 를 앞에서부터 한 글자씩 가져와 비교합니다. B를 먼저 다음 행에 가져옵니다.

그리고 첫 번째 RBKBGRBG 문자열 하나하나와 이 B를 비교합니다.

표에 들어가는 값은, LCS 길이의 값이 됩니다.

[1] R과 B는 서로 다름

[2] B와 B를 비교했더니 동일함

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

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

[4] B와 B -> 동일

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

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

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

• 맨 처음 {RB}와 {B}를 비교하여 1이 들어갔고, 그 다음 {RBK}와 {B}를 비교할 때 이것의 공통은 여전히 {B}로 그 길이가 1 입니다.

• 이 1이라는 값은 {RBK}와 {B}를 비교해서 얻은 1이기도 하지만, 엄밀히 말하자면 이전에 {RB}와 {B}를 비교했을 때 얻었던 1 인 것입니다. 즉, 이전의 값을 확인하여 사용하게 되므로 DP 관점에서 문제를 풀 수 있겠다는 것을 생각할 수 있습니다.

• 한 줄만 더 반복해 보겠습니다. 이제 다음 행에 BGKRBRKB 의 G를 추가합니다.

[5] R과 G -> 다름 (즉, {R}과 {BG}의 비교)

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

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

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

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

바로 이해가 되지 않으신다면 더 살펴보겠습니다.

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

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

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

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

[9] G와 G -> 동일. {RBKBG}와 {BG}와의 비교. 공통 부분의 길이는 2 인데,

• 이것은 {RBKB} 와 {B} 를 비교했을 때의 값보다 1이 증가한 의미가 됩니다.

• {RBKB}에서 {RBKBG}로, {B}에서 {BG}로 되어 두 값을 비교했더니 동일한 값 G가 나왔기에,

  직전의 값({RBKB}, {B}와 비교한 값)에서 1을 증가시켜 주는 것입니다.

• 이 직전의 값은 현재 위치를 기준으로 ‘대각선 왼쪽’ 값이 됩니다.

[10] 달랐을 때를 한번만 더 살펴보겠습니다.

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

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

찾아낸 규칙

• 문자열을 비교하여 같았을 때

  • 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값 + 1 이다.

• 문자열을 비교하여 달랐을 때

  • 현재 칸에 들어갈 값은 왼쪽과 위쪽의 값 중 더 큰 값이 들어간다.

이처럼 이전의 값이 앞으로 채워질 칸들에 대한 필요한 값이 되므로 DP로 볼 수 있습니다.

[LCS 알고리즘을 이용한 문제]

• SW Expert Academy의 [S/W 문제해결 응용] 8일차 - 이미지 유사도 검사 문제 (바로가기)
• https://www.acmicpc.net/problem/5582
• https://www.acmicpc.net/problem/9251
• https://www.acmicpc.net/problem/9252 (LCS 문자열 자체를 찾기)