[파이썬 풀이] 9251번: LCS(Longest Common Subsequence) - 백준

백준 9251번: LCS

알고리즘 분류: 문자열, 다이나믹 프로그래밍(DP)

파이썬(Python) 풀이

 

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

 

LCS(Longest Common Subsequence)란
최장 공통 부분 수열이라는 의미로 두 문자열 사이에서 모든 부분 수열이 되는 수열 중 가장 긴 문자열을 찾아내는 것이다.

 

문제

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

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

---

입력

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

---

출력

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

---

풀이

처음 이 문제를 접했을 때에는 와닿지 않았었다.

그래서 예시를 통해 접근하고자 하였다.

예제의 입력으로는 두 문자열 "ACAYKP"와 "CAPCAK"이 주어졌다.

그리고 출력으로는 "4"가 주어졌다.
이 경우에는 다음과 같이 비교하면 된다.

ACAYKP

CAPCAK

이를 통해 알 수 있는 점은, 순서가 유지되어야 한다는 것이다.

만약 두번째로 주어지는 문자열이 CAPCAK가 아닌 KACPAC라면 정답이 4라는 것을 보장할 수 없다는 것이다.

 

따라서 이 문제는 값을 누적하며 완전 탐색을 해야한다.

---

먼저 누적되는 값을 저장하는 테이블을 하나 준비한다.

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

이때 테이블의 크기는 각각 문자열 크기 + 1로 초기화 해주어야 한다.(가운데 흰색 테이블이라고 생각하면 된다.)

왜 문자열 크기 + 1인가요?
→ 그건 [i-1][j-1]번째의 값을 가져와야 하는데 0을 벗어나는 경우를 막기 위함으로 생각한다.

그리고 수를 누적하는 방법은 다음과 같다.

 

1)

i번째 행과 j번째 열의 문자가 같은 경우에, i-1번째, j-1번째의 table값 + 1을 해준다.

arr[i][j] = arr[i-1][j-1] + 1

 

2)

문자열이 다른 경우에는, i-1번째나 j-1번째의 table값 중 더 큰 값을 가져온다.

arr[i][j] = max(arr[i-1][j], arr[i][j-1])

 

첫번째 반복문을 수행하면 C가 같은 지점에서부터 나머지 부분이 1로 채워지게 된다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	0	0	0	0	0	0
P	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
K	0	0	0	0	0	0	0

 

 

두번째 반복문을 수행하면 A가 두번째로 나오는 부분에서 [i-1][j-1]값이 1이므로, 2가 되는 것을 확인할 수 있다.

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
K	0	0	0	0	0	0	0

 

직접 손으로, 또는 키보드로 나머지 값들을 채워보는 것을 추천한다.

 

그렇게 모든 반복문을 마치게 되면

	-	A	C	A	Y	K	P
-	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	1	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

마지막이 4가 나오는 것을 확인할 수 있다.

그 값이 LCS의 길이가 된다.

 

코드로 확인하면 다음과 같다.

 

str1 = input()
str2 = input()

arr = [[0 for _ in range(len(str1) + 1)] for i in range(len(str2) + 1)]

for i in range(1, len(str2) + 1):
    for j in range(1, len(str1) + 1):
        if str2[i-1] == str1[j-1]:
            arr[i][j] = arr[i-1][j-1] + 1
        else:
            arr[i][j] = max(arr[i-1][j], arr[i][j-1])

print(arr[-1][-1])