알고리즘/백준
[백준/Swift] 9251번: LCS
녕이
2023. 2. 24. 16:49
728x90
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
최장 공통부분 수열은 연속적으로 공통부분 수열을 찾는 게 아니라, 중간중간 다른 값이 있어도 된다..!
ACAYKP, CAPCAK 를 보면 ACAK
가능한 모든 경우를 구하려면 시간초과가 발생하므로 이럴 땐, dp!
이런 유형은 어떻게 해야 할지 모르겠어서 찾아봤더니,
| A C A Y K P
--------------
C |
A |
P |
C |
A |
K |
이런 식으로 진행하면 된다! 이런 방식은 생각 안 해봤는데 좋은 문제를 풀게 되었군.
배열 안 원소는 문자열 A(열)의 원소와 문자열 B(행)의 원소 사이의 최장 공통부분 수열 길이를 넣는 것이다!
DP를 사용하므로 앞 원소의 값을 사용해서 진행하면 되는데!
두 문자열 원소가 같다면, 문자열 A의 이전 문자, 문자열 B의 이전 문자까지 저장된 최장 공통 부분 수열 길이에 + 1
다르면, 문자열 A의 이전 문자까지의 최장 공통 부분 수열 길이, 문자열 B의 이전 문자까지의 최장 공통 부분 수열 길이의 최댓값
이렇게 앞의 값을 이용해서 진행하면, 가장 긴 길이가 나온다!
import Foundation
//input
let a = readLine()!.map{ String($0) }
let b = readLine()!.map{ String($0) }
var dp = [[Int]](repeating: [Int](repeating: 0, count: 1001), count: 1001)
//문자열 a를 기준으로
for i in 1...a.count {
//문자열 b를 순회
for j in 1...b.count {
//만약 같은 문자! -> 이전 칸 + 1 (공통문자열길이+1)
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])
}
}
}
print(dp[a.count][b.count])
//문자열 a 문자를 시작점으로 b와 비교
728x90