LCS(Longest Common Subsequence) : 최장 공통 부분문자열
두 문자열에서 "공통되는 가장 긴 부분문자열"을 찾는 알고리즘
여기서 subsequence는 꼭 연속하지 않아도 되는 부분문자열이다.
* 문자열에서 substring 과 subsequence의 차이 *
문자열 A가 있을 때,
- substring : 문자열 A의 연속하는 부분 문자열
- subsequence : 문자열 A에서 연속하지 않은 부분 문자열(연속해도 되고, 연속하지 않아도 됨)
즉, 다시 한번 짚고 넘어가면 LCS 알고리즘은 두 개의 문자열에서 subsequence를 찾는 알고리즘이다.
LCS 알고리즘은 DP(Dynamic Programming : 다이나믹 프로그래밍)을 이용한다.
LCS 알고리즘은 예제를 보면서 이해하는 것이 빠르다.
[예제]
문자열 ACDAGB, ADBGAG가 주어졌을 때, 두 문자열의 LCS를 구하여라.
두 문자열 중 아무거나 하나를 세로로 나열, 나머지 하나를 가로로 나열해보자.
일단, 첫번째 열과 행은 모두 0으로 채운다.
각 문자열 앞에 0을 둔 이유는 단지 코드를 짜는 과정에서 편의를 위해 이렇게 한 것이다.
이제 다음 행부터 채워보자.
각 칸이 의미하는 바는 이렇다.
특정 칸이 (i번째 열, j번째 행)에 위치하면, 해당 칸에는
ADBGAG 문자열의 0번째부터 i-1번째까지 부분문자열과
ACDAGB 문자열의 0번째부터 j-1번째까지 부분문자열간의 LCS 길이가 들어간다.
예를 들어, 아래 그림의 분홍색 칸에 들어갈 수는 무엇일까?
분홍색 칸은 (1번째 행, 1번째 열)에 위치한다.
ADBGAG 문자열의 0번째부터 0번째까지 부분문자열은 "A"이고,
ACDAGB 문자열의 0번째부터 0번째까지 부분문자열은 "A"이다.
이 때 A와 A의 최장 공통 부분문자열은 A가 되고 이때의 길이는 1이다. 그러므로 분홍색 칸에는 1이 들어간다.
그 다음 칸도 보자.
아래 그림의 분홍색 칸의 위치는 (1번째 행, 2번째 열)이다.
ADBGAG 문자열의 0번째부터 0번째까지 부분문자열은 "A"이고,
ACDAGB 문자열의 0번째부터 1번째까지 부분문자열은 "AC"이다.
A와 AC의 최장 공통 부분문자열은 A이다. 그리고 이때의 길이는 1이 되므로 분홍색 칸에는 1이 들어간다.
이런식으로 첫번째 행의 나머지 부분들도 채우면 아래와 같이 된다.
두번째 행도 마찬가지로 하면 된다.
ADBGAG의 0번째부터 1번째까지의 부분문자열인 "AD"와
ACDAGB의 0번째부터 0번째까지 부분문자열 "A",
0번째부터 1번째까지 부분문자열 "AC"
...
0번째부터 5번째까지 부분문자열 "ACDAGB"
과의 LCS 길이를 구해서 각각의 칸에 넣어주면 된다.
"AD" 와 "A" 의 LCS 길이는 1이고,
"AD" 와 "AC"의 LCS 길이도 1이다.
그런데 "AD" 와 "ACD"의 LCS 길이는 2가 된다.
각각의 부분문자열의 마지막 문자가 "D"로 동일하기 때문에 그전까지의 최장 공통 부분문자열은 "A"였는데, "D"가 추가됨에 따라 "AD"로 바뀌었다.
그러므로 그 전까지는 LCS 길이가 1이었는데, 둘 다 가지고 있는 "D" 문자가 새롭게 추가됨에 따라 LCS가 1에서 2로 증가되었다.
이를 통해 한가지 규칙을 알 수 있다.
i번째 문자와 j번째 문자가 동일하다면, i-1번째까지의 문자열과 j-1번째까지의 문자열 간의 LCS 길이에다가 +1을 해준 값이 해당 칸에 들어가게 된다.
dp[i][j] = dp[i-1][j-1] + 1;
즉, 왼쪽 위 대각선 칸에 있는 값 +1 이 현재 칸에 들어간다.
그렇다면 문자가 동일하지 않을 때는 어떤 값이 들어갈까?
"AD" 와 "ACDA" 의 LCS는
"AD" 와 "ACD" 의 LCS 길이 VS "A" 와 "ACDA"의 LCS 길이 중 더 긴 길이가 들어간다.
"AD" 와 "ACD" 의 LCS는 "AD" 이므로 길이가 2이고,
"A" 와 "ACDA"의 LCS는 "A" 이므로 길이가 1이기 때문에 둘 중에 더 긴 2가 "AD" 와 "ACDA" 의 LCS 길이가 된다.
i번째 문자와 j번째 문자가 동일하지 않다면, 왼쪽이나 위쪽 칸 중에 더 큰 수가 현재 칸에 들어간다.
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
이같은 규칙으로 나머지 칸도 채워보면 아래와 같이 완성된다.
가장 마지막 행 마지막 열에 있는 값이 두 문자열의 최장 공통 부분문자열의 길이가 된다.
ACDAGB 와 ADBGAG의 LCS의 길이 : 4
소스코드 :
백준 9251번 : LCS 의 소스코드이다.
[응용1] 만약에 LCS의 길이를 구하는 것이 아니라 LCS 자체를 구하는 것이 문제라면 어떻게 구할까?
위 예제에서 두 문자열의 LCS는 "ADAG" 이다. 길이를 구하는 것이 아니라 "ADAG" 자체를 구하는 것이
문제라면 가장 마지막 칸부터 규칙을 따라 거슬러 올라가면서 찾을 수 있다.
가장 마지막 칸의 4는 어디서 나온 값이었나?
문자가 다른 경우, 왼쪽이나 위쪽 칸 중에 더 큰 값이 들어갔었다.
마지막칸의 경우 바로 왼쪽칸에는 4가, 위쪽칸에는 3이 들어가있으므로 왼쪽칸으로부터 얻어진 값임을 알 수 있다.
-> 그러면 왼쪽칸으로 거슬러 이동한다.
다시 노란색칸(dp[6][5])에서 왼쪽과 위쪽을 봤더니 왼쪽칸에는 3, 위쪽칸에도 3이 들어가 있으므로 4와 같은값이 하나도 없다. 그렇다면 노란색칸의 4는 왼쪽위 대각선칸 +1 로 얻어진 값일 것이다. 그리고 이 뜻은 현재 두 문자열의 마지막 문자가 동일한 것을 의미한다.(여기서는 "G"로 동일)
이때의 "G"가 LCS의 마지막 문자가 된다. -> ○○○G
-> 왼쪽위 대각선칸으로 거슬러 이동한다.
마찬가지로 dp[5][4] 의 왼쪽칸은 2, 위쪽칸은 2이므로 dp[5][4]의 3 역시 왼쪽위 대각선칸 + 1 로 얻어졌을 것이다.
이 의미는 현재 두 문자열의 마지막 문자가 동일하다는 것을 의미(여기서는 "A"로 동일)하고,
LCS의 뒤에서 두번째 문자가 "A"가 된다. -> ○○AG
그리고 왼쪽위 대각선으로 거슬러 이동한다.
계속 이런 방식으로 거슬러 올라가면서 특정 칸의 값이 왼쪽위 대각선으로부터 얻어진 것일 때만 LCS에 포함된 문자열로 여긴다.(노란색칸)
그래서 답은 노란색칸으로 얻어진 "ADAG"가 된다.
소스코드 :
백준 9252번 : LCS 2 의 소스코드이다.
[응용2] 만약에 연속되는 최장 공통 부분문자열만을 구해야하는 문제라면?
subsequence를 구하는 것이 아니라 substring을 구해야 한다면 어떻게 해야할까?
그럴 때는 두 문자열의 마지막 문자가 동일할 때만 dp[i][j]에 넣어주면 된다.
subsequence를 구할 때는
- 문자가 동일한 경우, dp[i][j] = dp[i-1][j-1] + 1
- 문자가 동일하지 않은 경우, dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
이렇게 두 가지 규칙으로 나누었지만,
substring을 구해야 한다면,
- 문자가 동일한 경우, dp[i][j] = dp[i-1][j-1] + 1
- 문자가 동일하지 않은 경우, 아무 처리도 하지 않음
위의 예제를 그대로 적용하여 표를 만들면 다음과 같이 된다.
분홍색칸의 수 중에 가장 큰 값이 2 이므로 답은 2가 된다.
소스코드 :
백준 5582번 : 공통 부분 문자열 의 소스코드이다.