[BaekJoon] LCS

Swift Study 이주의 문제 2

9251번: LCS

---

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

---

유튭에서 강의를 참고함. 재귀와 동적 계획법을 모두 알려주셔서 각 기법을 좀 더 잘 이해하고 명확하게 알 수 있어서 좋았다

동적 계획법

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

각 문자열로 이루어진 행렬을 만들고 문자가 같은경우 좌측 상단 값의 +1, 다른경우 좌측과 상단값중 최대값을 가져온다. 마지막 값이 수열중 가장 긴 값이 된다.

let str1: [String] = [""] + readLine()!.map{String($0)}
let str2: [String] = [""] + readLine()!.map{String($0)}
let (len1, len2) = (str1.count - 1, str2.count - 1)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: len2 + 1), count: len1 + 1)

for i in 1...len1 {
    for j in 1...len2 {
        if str1[i] == str2[j] {
            dp[i][j] = dp[i - 1][j - 1] + 1
        }
        else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        }
    }
}
print(dp[len1][len2])

 

str에는 하단 반복문을 맞추기 위해서 [""]를 추가했다.