➊ 문제 정의
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK 두 문자열이 주어진다면,
ACAYKP의 부분 수열로는 A, AP, CYK, ACAK 등이 있고
CAPCAK의 부분 수열로는 A, AP, PCA, ACAK 등이 있다.
두 문자열 모두의 부분 수열이 되는 것 중 가장 긴 것은 ACAK이다.
따라서 LCS는 ACAK이다.
위와 같이 입력으로 두 문자열이 들어왔을 때 LCS의 길이를 출력하는 코드를 작성하는 것이 우리의 목표이다!
➋ 풀이 과정
두 문자열의 LCS의 길이를 찾기 위해,
순차적으로 작은 문제를 풀어나가며 이를 바탕으로 큰 문제를 푸는
다이나믹 프로그래밍을 해야 한다.
2차원 DP 배열을 사용하여 LCS의 길이를 누적하여 계산한다.
(1행) ACAYKP와 C를 비교하여 LCS의 길이를 찾는다.
(2행) ACAYKP와 CA를 비교하여 LCS의 길이를 찾는다.
(3행) ACAYKP와 CAP를 비교하여 LCS의 길이를 찾는다.
(4행) ACAYKP와 CAPC를 비교하여 LCS의 길이를 찾는다.
(5행) ACAYKP와 CAPCA를 비교하여 LCS의 길이를 찾는다.
(6행) ACAYKP와 CAPCAK를 비교하여 LCS의 길이를 찾는다.
1행에서는 ACAYKP와 C를 비교하고 있다.
이를 더 세분화해서 살펴보자면,
(1열) A와 C를 비교하여 LCS의 길이를 찾는다.
(2열) AC와 C를 비교하여 LCS의 길이를 찾는다.
(3열) ACA와 C를 비교하여 LCS의 길이를 찾는다.
(4열) ACAY와 C를 비교하여 LCS의 길이를 찾는다.
(5열) ACAYK와 C를 비교하여 LCS의 길이를 찾는다.
(6열) ACAYKP와 C를 비교하여 LCS의 길이를 찾는다.
이처럼 작은 문제부터 해결하고 이를 누적하여 다음 단계의 문제를 해결한다.
그렇다면 다음 단계의 LCS의 길이를 어떻게 계산해야 할까?
먼저 2가지 경우로 나누어 생각할 수 있다.
- (i행 문자 = j열 문자)
- (i행 문자 ≠ j열 문자)
① (i행 문자 = j열 문자)인 경우
(i = 3, j = 6)
P가 같은 부분을 예시로 들어보겠다!
이 부분은 정확히 말하자면 ACAYKP와 CAP을 비교하고 있다.
이때 두 문자열 모두 마지막 문자가 P이기 때문에 아래의 식을 도출할 수 있다.
ACAYKP와 CAP의 LCS의 길이
= ACAYK와 CA의 LCS의 길이 + 1
즉, DP[3][6] = DP[2][5] + 1이고
이를 일반화하면 DP[i][j] = DP[i-1][j-1] + 1 라는 식을 도출할 수 있다.
② (i행 문자 ≠ j열 문자)인 경우
(i = 5, j = 4)
i행 문자가 A이고 j열 문자가 Y인 부분을 예시로 들어보겠다!
CAPCA와 ACAY의 마지막 문자는 같지 않기 때문에
이전의 LCS 길이보다 클 수 없다.
따라서 이전의 값 중 최댓값을 그대로 가져와서 사용한다.
이를 일반화하여 식으로 표현하면 아래와 같다.
DP[i][j] = max(DP[i][j-1], DP[i-1][j])
위와 같은 방식으로 이전에 구해둔 값을 활용하여 다음 값을 계산한다!
최종적으로 DP 배열의 마지막 값이 두 문자열의 LCS의 길이가 된다.
➌ 정답 코드
위의 해결 과정을 코드로 변환하면 다음과 같다.
A = ' ' + input()
B = ' ' + input()
dp = [[0 for _ in range(len(B))] for _ in range(len(A))]
for i in range(1, len(A)):
for j in range(1, len(B)):
if A[i] == B[j]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[-1][-1])잘못된 정보, 오탈자를 발견하면 편하게 댓글로 말씀해주시면 감사하겠습니다 🙂
