[백준] 9251 LCS

J. Hwang·2025년 1월 28일

Coding python 코딩테스트

coding test

목록 보기

91/108

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

내 풀이

import sys
input = sys.stdin.readline

a = input().strip()
b = input().strip()

dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]

for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            
print(dp[len(a)][len(b)])

코멘트

우선 LCS라는 개념부터 모르고 있었다. 분명 ACAYKP에서 중간에 Y가 껴있는데도 ACAK라는 공통 문자가 나온다는 것이 이해되지 않았다. 알고 보니 내가 "부분 문자열(substring)"과 "부분 수열(subsequence)"를 혼동하고 있었던 것이다. 부분 문자열은 연속된 문자열을 의미하고, 부분 수열은 문자의 순서는 유지하되 일부 문자를 건너뛸 수 있는 경우를 의미한다고 한다.

이 문제는 dp 테이블을 만들어서 해결할 수 있다. 먼저 string 1을 세로로 써넣고, string 2를 가로로 써넣은 뒤 맨 처음에 dummy 행, dummy 열을 하나씩 끼워 넣는다. (연산을 편하게 하기 위해서)

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

그런 다음 각 문자를 알파벳 하나씩 비교하면서 아래 규칙에 따라 dp 테이블에 값을 써넣는다.

두 문자가 다를 때는 i행 (j-1)열과 (i-1)행 j열의 수를 비교하여 그 중 더 큰 값(max)을 써넣는다.
두 문자가 같을 때는 (i-1)행 (j-1)열의 수 + 1를 채워넣는다.

예를 들어, CAPCAK의 맨 첫 글자 C와 ACAYKP의 맨 첫 글자 A는 다르므로, 1행 0열의 0과 0행 1열의 0 중 더 큰 값 0을 써 넣는다. 그 다음, CAPCAK의 두 번째 글자 A와 ACAYKP의 맨 첫 글자 A는 같으므로, 0행 1열의 0에 1을 더해서 1을 써 넣는다.