[Algorithm] 백준 - 9251번 LCS (Swift)

문제 소개

유명한 다이나믹 프로그래밍 문제인 LCS(Longest Common Subsequence) 문제를 풀어보았다.

문제 풀이

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

이 블로그... 너무 설명을 잘해주셨다. 아래와 같이 Subsequence를 탐색하면 된다.

1. LCS 2차원 배열 선언

2차원 배열을 선언해준다. first와 second의 첫글자를 가져와서 변수명을 지었다.

let f = Array(readLine()!)
let s = Array(readLine()!)
var lcs = Array(repeating: Array(repeating: 0, count: s.count + 1), count: f.count + 1)

2. LCS 구하기

값이 같다면 lcs[i-1][j-1] + 1로 lcs배열에 적용하고, 값이 다르다면 lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])를 배열에 적용해준다.

for i in 1...f.count {
    for j in 1...s.count {
        if f[i-1] == s[j-1] {
            lcs[i][j] = lcs[i-1][j-1] + 1
        } else {
            lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
        }
    }
}

정답 코드

let f = Array(readLine()!)
let s = Array(readLine()!)
var lcs = Array(repeating: Array(repeating: 0, count: s.count + 1), count: f.count + 1)

for i in 1...f.count {
    for j in 1...s.count {
        if f[i-1] == s[j-1] {
            lcs[i][j] = lcs[i-1][j-1] + 1
        } else {
            lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
        }
    }
}

print(lcs[f.count][s.count])

역시 풀때마다 감탄이 나오는 다이나믹 프로그래밍...