9251: LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

LCS는 가장 긴 공통 부분 수열을 찾는 유형의 문제를 이르는 말인 것 같다.
우선 풀이는 완전탐색(브루트포스), 동적계획법이 가능하다.
어느 블로그를 찾아보니 LCS가 두 가지 문제 유형으로 나뉜다고 한다.
1. Longest Common Substring
2. Longest Common Subsequence
 
이 문제는 2번이다. 1번은 가장 긴 공통 문자열을 찾는 문제라 연속된 공통부분만 찾아주면 된다.
이 경우, 완전탐색하지 않고 백트래킹으로도 해결 가능하다.
 
원리를 요약하면 이렇다.
A, B 문자열이 주어지고 각 문자열의 길이를 a, b라고 한다.
A[0]부터 A[a-1]까지 각 문자를 B[0]부터 B[b-1]까지 순차적으로 비교한다.
a행 b열의 2차원 배열 dp[i][j]를 만들어 A[i], B[j]까지의 비교 결과를 저장한다.
비교 결과는 A[i]와 B[j]가 같은 경우와 다른 경우로 나뉜다.
 

1. A[i]가 B[j]와 같은 경우

A[i - 1], B[j - 1]까지의 비교 상황에서 다음 문자열이 같은 것으로 볼 수 있다.
A[i - 1]과 B[j - 1]이 같아도 달라도 여기까지의 비교 값보다 1개의 문자가 더 같은 것으로 볼 수 있다.
dp[i][j] = dp[i - 1][j - 1] + 1
 

2. A[i]가 B[j]와 다른 경우

A나 B 둘 중 하나만 이 전 문자까지 비교한 상황을 불러온다.
두 문자가 일치하지 않았다면 A나 B나 다음 문자를 확인해야 한다.
A[i + 1]이나 B[j + 1]로 넘어가는 것이 아니라 이전 상태인 A[i - 1], B[j]나 A[i], B[j - 1] 중 더 많은 부분 수열을 기록한 데이터를 가져온다.
dp[i][j] = max(dp[i - 1][j], dp[i][j  - 1])

이렇게 모든 배열의 데이터를 채우고 나면 두 문자열의 끝 값을 비교한 후의 부분수열 dp[a][b]는 가장 긴 부분수열만을 끌고 왔기 때문에 가능한 모든 경우의 최대 길이를 나타낸다.