[백준] (9251) LCS [Python]

문제 링크

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

문제

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

• 입력 : 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
• 출력 : 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력	예제 출력
ACAYKP CAPCAK	4

---

LCS란?

두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 문자열 중 가장 긴 것을 찾는 문제다.

부분 수열이란?

어떤 문자열에서 일부 문자를 삭제해 얻을 수 있는 문자열. 문자들의 순서는 유지되어야 함.

• 문자열 A: ACDBE
• 부분 수열: ABE, AD, CDE 등

해결 아이디어: 동적 계획법(DP)

LCS 문제는 전체 탐색으로 풀면 지수 시간 복잡도 O(2ⁿ)이 걸린다. 하지만 중복되는 부분 문제Subproblem가 존재하므로 DP를 활용해 효율적으로 해결할 수 있다.

 

1. 문제 분석하기

LCS는 문자열을 이용한 대표적인 동적 계획법 문제이다. 이런 종류의 문제를 풀기 위해서는 다음과 같이 각 문자열을 축으로 하는 2차원 리스트를 생성해야 한다.

	A	C	A	Y	K	P
C
A
P
C
A
K

이렇게 구상한 2차원 리스트가 바로 점화식 테이블이 된다. 테이블에 저장하는 값은 각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이다. 예를 들어, 색칠된 칸은 ACAY와 CA 문자열로 만들 수 있는 최장 공통 부분 수열의 길이 값인 2로 채워진다.

 

2. 점화식 정의

dp[i][j] = LCS(A[0:i], B[0:j])의 길이
if A[i-1] == B[j-1]일 경우:
	dp[i][j] = dp[i-1][j-1] + 1
같지 않을 경우:
	dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

3. 점화식 유도

우리는 dp[i][j]를 구하고 싶은 것이다. 이걸 알기 위해선 두 문자열의 마지막 글자에 주목해야 한다.

• A의 i번째 문자: A[i-1]
• B의 j번째 문자: B[j-1]

여기서 두 가지의 경우로 나뉠 수 있다.

• A[i-1] == B[j-1] → 두 문자가 같을 때 : 이 경우, 공통 부분 수열에 포함시킬 수 있다. 그러면 dp[i][j]는 A[i-1]과 B[j-1]를 제외한 앞부분인 dp[i-1][j-1]에 1을 더해주면 된다. → dp[i][j] = dp[i-1][j-1] + 1
• A[i-1] != B[j-1] → 두 문자가 다를 때 : 이 경우, 둘 중 하나의 문자는 공통 부분 수열에 포함되지 않기 때문에 두 가지 경우 중 최댓값을 선택해야 한다.
  • A의 i번째 문자는 제외하고 비교: dp[i-1][j]
  • B의 j번째 문자는 제외하고 비교: dp[i][j-1]
  • 따라서, dp[i][j] = max(dp[i-1][j], dp[i][j-1])

   A = A C A Y K P
   B = C A P C A K
         ↑ ↑ ↑ ↑   ← 이게 공통 부분 수열: C A P K

dp 테이블은 이런 식으로 두 문자열을 하나씩 비교하면서
"지금 문자를 포함할 수 있나?" → "이전 상태에서 가장 긴 수열은 뭐였지?"
를 반복해서 채워나가는 구조.

 

4. DP 테이블 초기 상태 (0으로 채워진 상태)

우선 테이블은 (len(A)+1) × (len(B)+1) 크기이며, dp[0][*]와 dp[*][0]은 항상 0으로 시작한다 (빈 문자열 비교).

     ''  C  A  P  C  A  K
   -----------------------
''|  0  0  0  0  0  0  0
A |  0  .  .  .  .  .  .
C |  0  .  .  .  .  .  .
A |  0  .  .  .  .  .  .
Y |  0  .  .  .  .  .  .
K |  0  .  .  .  .  .  .
P |  0  .  .  .  .  .  .

 

5. 실제 DP 값 채우기

표를 하나씩 따라가며 규칙대로 채워보자. 각 셀 dp[i][j]의 값은 다음 기준으로 계산한다.

• 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])

6. 최종 DP 테이블

     ''  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

 

분석 포인트

• dp[6][6] = 4 → 최종 LCS 길이 = 4
• 공통 부분 수열: CAPK
  • C (A[1], B[0])
  • A (A[2], B[1])
  • P (A[5], B[2])
  • K (A[4], B[5])

요약

• 표를 보면 점점 왼쪽 위 → 오른쪽 아래로 값이 축적되는 구조
• 일치하는 문자가 발견되면 대각선에서 +1
• 일치하지 않으면 왼쪽 또는 위쪽의 최댓값을 사용
• 이 과정을 통해 LCS를 점진적으로 완성

정리

상황	의미	점화식
A[i-1] == B[j-1]	두 문자가 같으니 공통 수열에 넣자	dp[i][j] = dp[i-1][j-1] + 1
A[i-1] != B[j-1]	두 문자가 다르니 하나를 버리고 더 긴 쪽을 선택하자	dp[i][j] = max(dp[i-1][j], dp[i][j-1])

---

코드

A = input()
B = input()
a, b = len(A), len(B)

dp = [[0] * (a+1) for _  in range(b+1)]
for i in range(1, b+1):
    for j in range(1, a+1):
        if B[i-1] == A[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[-1][-1])