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

# LCS 알고리즘이란?

두 개의 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 수열을 찾는 알고리즘

예를 들어, 문자열 awszosw 와 asofw 가 주어지는 경우 공통으로 나타나는 가장 긴 수열은 asow 이다.

이를 풀기 위해서는 DP 를 활용해야 하는데, LIS 및 LCS 때와는 달리 2개의 문자열이 주어지기 때문에 2차원 DP 테이블을 이용해야한다.

LCS 알고리즘에서 문제의 정답 문자열은 하나가 아닌, 여러 개일 수도 있다.
만약 ACBED 와 ABC 가 주어진다면 AB 가 되거나 AC 가 될 수도 있다.

이 알고리즘은 두 문자열의 길이에 비례해 작동하기 때문에 O(m * n) 의 시간복잡도를 가진다.

# LCS 알고리즘 진행 순서를 알아보자

2차원 배열을 선회하기 위해 for(i in 1 .. m){ for(j in 1 .. n)} 실행.
i = ABC, j = ACBED

	0	A	C	B	E	D
0	0	0	0	0	0	0

처음 dp[0][j] 의 경우 모두 일치하는 문자열이 없으므로 0이다.
우리는 이러한 이유로 i,j 를 1부터 시작한다.

	0	A(1)	C(2)	B(3)	E(4)	D(5)
0	0	0	0	0	0	0
A(1)	0	?

i 가 1로 증가하고 j를 순회를 시작하였을 때, i 문자와 j 문자가 같다는 것을 알게 되었다.

문자가 같으므로 dp[i][j] = dp[i - 1][j - 1] + 1 을 넣어준다.

	0	A	C	B	E	D
0	0	0	0	0	0	0
A	0	1	?

이번에는 C != A 이다. 문자가 서로 다르므로 dp[i][j] = kotlin.math.max(dp[i - 1][j], dp[i][j - 1]) 을 해준다.

dp[i - 1][j] 와 dp[i][j - 1] 중 최대값을 dp[i][j] 에 넣는 이유는 str1[i] 와 str2[j] 가 다를 때, 둘 중 하나는 LCS 에 포함되지 않으므로 더 긴 값을 넣어줘야 하기 때문이다.

이제 이것을 반복하면 다음과 같은 표가 나오게 된다.

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

# 전체 코드

fun lcs(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val str1 = br.readLine()
    val str2 = br.readLine()
    val dp = createLcsDpTable(str1, str2)

    bw.write(getLcsString(str1, str2, dp))
    bw.flush()
    bw.close()
    br.close()
}

// LCS DP 구하기 (DP[m][n] = LCS 개수)
private fun createLcsDpTable(str1: String, str2: String): Array<IntArray>{
    val m = str1.length
    val n = str2.length
    val dp = Array(m + 1){ IntArray(n + 1) }

    for(i in 1 .. m){
        for(j in 1 .. n){
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = kotlin.math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    return dp
}

// LCS 문자열 구하기
private fun getLcsString(str1: String, str2: String, dp: Array<IntArray>): String {
    var i = str1.length
    var j = str2.length
    val lcs = StringBuilder()

    while (i > 0 && j > 0) {
        //  두 문자가 같다면 LCS에 포함되는 문자
        if (str1[i - 1] == str2[j - 1]) {
            lcs.append(str1[i - 1])
            i--
            j--
        }
        // 두 문자가 다르다면, 더 큰 값을 가진 쪽으로 이동
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--
        } else {
            j--
        }
    }

    return lcs.reversed().toString()
}