백준 9251

백준

황태건 2023. 5. 14. 23:14

9251번: LCS

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

www.acmicpc.net

동적 프로그래밍을 이용해 간단하게 풀 수 있는 문제이다 (난 아니여서 답지 봄)

두 문자열 s1, s2에 대하여 dp[i][j] = s1[i], s2[j]까지의 LCS라고 할 때,

dp[i][j]가 가질 수 있는 값의 종류는 다음과 같다.

1. i 또는 j가 0일 경우

두 문자열은 공통 문자를 가질 수 없으므로 0

2. 둘 다 0이 아닌 경우 중 s1[i] = s2[j]일 경우

dp[i-1][j-1]까지의 LCS에서 s1[i], s2[j]를 추가하면 되므로 dp[i-1][j-1] + 1

3. 둘 다 0이 아닌 경우 중 s1[i] != s2[j]일 경우

s1과 s2의 LCS는 dp[i-1][j]나 dp[i][j-1] 중 더 큰 쪽 (이해 잘 안 됐던 부분)

이므로 max(dp[i-1][j], dp[i][j-1])

이를 활용하여 반복문을 사용해 2차원 배열 dp를 순서대로 채워나간다.

배운 내용 :

LCS는 두 문자열 길이 각각에 따라 달라질 수 있으므로 input size가 (m,n)이며,

따라서 optimal substructure도 이에 맞게 구성해야한다.

DP 문제를 풀 때는 항상 '현재 값을 구하기 위해 어떤 값이 계산되어있어야 하는가'를 고려해야 한다.