[백준(Baekjoon)] 9251 LCS

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

ACAYKP
CAPCAK

 

예제 출력 1 

4

 

 

---

나의 코드

[Python(파이썬)]

a = '0' + input()
b = '0' + input()
lena, lenb = len(a), len(b)
lcs = [[0] * (lenb) for _ in range(lena)]

for i in range(1, lena):
    for j in range(1, lenb):
        if a[i] == b[j]:
            lcs[i][j] = lcs[i - 1][j - 1] + 1
        else:
            lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j])

print(lcs[-1][-1])

---

풀이

• LCS(Longest Common Subsequence, 최장 공통 부분 수열) 설명 페이지

[Algorithm] LCS (최장 공통 부분 수열, 최장 공통 부분 문자열)

 

이미 예전에 LCS 알고리즘을 정리한 적이 있어서 이 문제는 보자마자 어떻게 풀어야할지 생각이 떠올랐다. 

 

위 포스팅에도 나와있듯 LCS에는 2가지가 있다. 

 

LCS의 2가지

• Longest Common Subsequence (최장 공통 부분 수열) : 전체 문자열에서 꼭 연속적이지는 않은 부분 문자열
• Longest Common Substring (최장 공통 부분 문자열) : 전체 문자열에서 연속된 부분 문자열

 

이 문제는 두가지 中 연속적이지는 않은 부분 문자열을 구하는 위의 경우에 해당한다. 

예제 1)
str1 : ACAYKP
str2 : CAPCAK

 

Longest Common Subsequence (최장 공통 부분 수열)

공통 부분 수열 中 길이가 가장 긴 부분 수열

ex) 
str1 : 'ABEWHCJ'
str2 : 'AEWHABJ'
Longest Common Subsequence - 'AEWHJ'

 

- str1[i]와 str[j]가 같으면 대각선 왼쪽 위를 가리키며 LCS[i][j] = LCS[i-1][j-1] + 1을 해준다. (대각선 왼쪽 위 방향의 값 + 1)

 if a[i] == b[j]:
	lcs[i][j] = lcs[i - 1][j - 1] + 1

- str1[i]와 str[j]가 다르다면, 좌측이나 위에 있는 숫자 중 큰 값을 가리키며 같은 값을 가진다. 동일한 값일 때는 위의 값을 가리킨다.  

 max(lcs[i][j - 1], lcs[i - 1][j])

- 제일 좌측 하단에서부터 시작해 화살표 방향으로 따라가면서 대각선 방향을 가리키는 부분의 문자를 나열하면 최장 공통 부분 수열LCS가 된다. 

 

※ LCS[0][0-7]과 LCS[0-7][0]의 행은 0으로 초기화 해야한다. (가로, 세로 첫번째 행은 0으로 초기화)

-> 아래의 조건으로 생각해보면  str1 : 'ABEWHCJ' , str2 : 'AEWHABJ'에서 첫번째 A를 만났을 때 LCS[i-1][j-1]을 참조해야하는데 만약 가로, 세로 첫번째 행을 0으로 초기화 하지 않았다면 LCS[-1][-1]를 참조해  ERROR가 날 것이다. 

# 문자열 맨 앞에 0을 추가해줌으로써 LCS 배열 가로, 세로 첫번째 줄은 0으로 초기화
a = '0' + input()
b = '0' + input()

 

이 문제는 LCS 문자열을 구하는 것이 아니라 LCS의 길이만 출력하면 되기 때문에 2차원 리스트의 제일 마지막 숫자(LCS[-1][-1])만 출력 해주면 된다. 

 

---

문제 출처

9251번: LCS