[백준 #9251] LCS - Python

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

9251번: LCS

---

---

두 문자열의 최장 공통부분 수열(문자열)을 구하는 방법은 생각보다 간단하다.

두 문자열의 맨 첫 글자부터 한 글자씩 비교하면 된다.

 

한 글자씩 비교할 때, 가능한 경우의 수는 크게 2가지이다.

 

CASE1:

1. 비교하는 두 글자가 동일하다.
2. 비교하는 두 글자가 동일하지 않다.

비교하는 두 글자가 동일하다면, LCS의 길이를 1 늘리고 다음 글자를 비교한다.(CASE1을 반복)

비교하는 두 글자가 동일하지 않다면, 다시 경우의 수가 3가지로 나뉘게 된다.(CASE2로 이동)

 

CASE2:

1. 첫 번째 문자열의 비교했던 글자와 두 번째 문자열의 다음 비교할 글자가 동일하다.
2. 두 번째 문자열의 비교했던 글자와 첫 번째 문자열의 다음 비교할 글자가 동일하다.
3. 위와 같이 비교한 경우에도 일치하지 않는다.

위 1,2번의 경우에는,  LCS의 길이를 1 늘리고 다음 글자를 비교한다.(CASE1로 이동)

3번의 경우에는, 다시 그 다음 글자와 비교하면 된다.(CASE2를 반복)

 

 

예를 들어, APPLE와 APE를 비교한다고 할 때,

A P P L E

A P E

A 와 그 다음 글자인 P 까지는 동일하다. (AP 까지의 LCS = 2)

이 후 P와 E를 비교할 때, 동일하지 않으므로 APPLE의 다음 글자 L과 E를 비교한다.(APE는 E 이후의 글자가 없으므로 비교할 다음 문자가 없다.)

역시 L과 E가 동일하지 않으므로, APPLE의 다음 글자 E과 E를 비교한다.

동일하고 두 문자열 모두 끝자리에 도달했으므로 APPLE과 APE의 LCS는 3이 된다.

 

 

위와 같은 방식을 코드로 구현하면 다음과 같다.

이 때, 똑같은 비교를 반복하지 않도록, 각 문자열의 특정 index에서의 lcs는 length_table에 저장하여 재사용하도록 한다.(DP memoization 사용)

#시간초과
import sys

sys.setrecursionlimit(10000)
str1 = list(sys.stdin.readline().rstrip())
str2 = list(sys.stdin.readline().rstrip())

str1_length = len(str1)
str2_length = len(str2)

#length_table[i][j]는 str1[i:]과 str2[j:]를 비교했을 때 나오는 lcs를 저장
length_table = [[-1 for i in range(str2_length)] for j in range(str1_length)]


def lcs(index1, index2):

    global str1, str2, length_table, str1_length, str2_length

    #str1이나 str2의 끝에 도달했다면, 더는 겹치는 것이 없는 것
    if index1 ==str1_length or index2 ==str2_length:
        return 0

    #이미 저장된 lcs가 있다면 그것을 사용
    if length_table[index1][index2] != -1:
        return length_table[index1][index2]

    #두 문자가 같다면 그 다음 문자부터 비교했을 때의 값+1이 lcs
    if str1[index1] == str2[index2]:
        length_table[index1][index2] = lcs(index1+1, index2+1)+1
    else:
        #두 문자가 같지 않다면
        length_table[index1][index2] = max(
            # str1의 다음 문자와 비교를 하거나
            lcs(index1 + 1, index2),
            # str2의 다음 문자와 비교를 하거나
            lcs(index1, index2 + 1)
        )

    return length_table[index1][index2]

print(lcs(0,0))

다만, 위와 같이 구현하였을 때에는 백준에 제출하였을 때, 시간초과로 인한 오답으로 채점된다.

 

이는 아무리 재사용을 이용해 반복을 줄인다고 해도, 재귀함수의 호출은 그대로 이루어졌다가 return된다는 문제점 때문이다. 문자열의 길이가 충분히 길어지면 재귀함수의 호출이 많아지고, 그에 따라 함수 호출에 대한 오버헤드가 커져서 성능이 저하될 수 있다.

---

위와 같은 문제점을 해결하기 위해서는 재귀함수를 사용하지 않는 방식으로 바꾸면 된다.

위 코드에서 재귀함수가 호출되는 이유는 다음 문자와 비교할 때, 아직 다음 문자에서의 LCS를 알지 못하기 때문이다.

그렇다면 다음 문자에서의 LCS를 이미 알고 있다면 재귀함수가 호출될 필요가 없다.

 

문제점을 해결한 정답 코드는 아래와 같다.

import sys

str1 = list(sys.stdin.readline().rstrip())
str2 = list(sys.stdin.readline().rstrip())

str1_length = len(str1)
str2_length = len(str2)

#length_table[i][j]는 str1[i:]과 str2[j:]를 비교했을 때 나오는 lcs를 저장
length_table = [[0 for j in range(str2_length+1)] for i in range(str1_length+1)]

#최종적으로 얻고 싶은 것은 length_table[0][0]
#재귀가 아니므로 끝에서부터 채워와야한다.
for index1 in range(str1_length-1,-1,-1):
    for index2 in range(str2_length-1,-1,-1):
        #두 문자가 같다면, 그 앞에서의 lcs에 1을 더한 값이 최댓값
        if str1[index1] == str2[index2]:
            length_table[index1][index2] = length_table[index1+1][index2+1] + 1
        else:
            # 두 문자가 같지 않다면
            length_table[index1][index2] = max(
                # str1의 다음 문자와 비교를 하거나
                length_table[index1 + 1][ index2],
                # str2의 다음 문자와 비교를 하거나
                length_table[index1][index2+1]
            )

# print("========lcs table========")
# print(" ", end=" ")
# for char in str2:
#     print(char, end =" ")
# print("")
# for i in range(len(length_table)-1):
#     print(str1[i], end = " ")
#     for j in range(len(length_table[0])-1):
#         print(length_table[i][j], end=" ")
#     print("")
# print("========================\n")

print(length_table[0][0])

위 코드는 앞에서부터가 아니라 뒤에서부터 비교를 시작함으로써, 어떤 문자를 비교할 때 그 다음 문자에서의 LCS가 이미 length_table에 저장되어 있도록 한다.

 

재귀함수를 이용해 알고리즘을 구현했을 때, DP table을 활용했음에도 시간초과가 발생한다면, 이렇게 재귀가 사용되지 않는 코드로 바꾸어 보자.

---

이해를 돕기 위해 첨부하자면, 이 문제의 예시를 이용해 LCS table을 만든 결과는 다음과 같다.

 

예제 입력:

• ACAYKP
• CAPCAK