백준 - LCS 2 (9252)

let A = Array(readLine()!)
let B = Array(readLine()!)

var dp = Array(repeating: Array(repeating: 0, count: B.count + 1), count: A.count + 1)

for i in 1...A.count {
    for j in 1...B.count {
        if A[i - 1] == B[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1
        } else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        }
    }
}

// LCS 찾기
var LCS = ""
var row = A.count
var col = B.count

while row != 0 && col != 0 {
    if A[row - 1] == B[col - 1] {
        LCS += String(A[row - 1])
        row -= 1
        col -= 1
    } else {
        if dp[row][col - 1] > dp[row - 1][col] {
            col -= 1
        } else {
            row -= 1
        }
    }
}

print(dp[A.count][B.count])
print(String(LCS.reversed()))

최장 공통 수열 길이 구하기

각 문자열을 축으로 하는 2차원 배열을 생성한다. 이때 이 배열의 각 값은 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이이다.

두 문자열에서 현재 비교하고 있는 문자가 같으면 배열의 대각선 왼쪽 위 값에 1을 더한 값을 저장한다. (dp[i][j] = dp[i - 1][j - 1] + 1)

비교한 값이 다르면 현재 자리의 왼쪽 값과 위의 값 중 큰 값을 저장한다. (dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) )

이 과정을 반복해서 배열을 채우면 배열의 끝 값이 LCS의 길이가 된다.

최장 공통 수열 찾기

dp 배열의 마지막부터 탐색해서 두 문자열의 현재 자리 인덱스의 문자가 같으면 그 문자를 정답 변수에 추가하고 대각선 왼쪽 위로 이동한다.

두 문자가 다르면 왼쪽 값과 위의 값 중 저장된 값이 큰 값으로 이동한다.