[BOJ][🟡5][백준#09251] LCS

문제 출처

BAEKJOON Online Judge #9251

문제

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

입력

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

출력

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

예제

입력

ACAYKP
CAPCAK

출력

4

My Sol

A, B = input(), input()
al, bl = len(A), len(B)

mat = [[0]*(bl+1) for _ in range(al+1)]
for i in range(1, al+1):
    a = A[i-1]
    for j in range(1, bl+1):
        b = B[j-1]
        mat[i][j] = max(mat[i][j-1], mat[i-1][j])
        if a == b:
            mat[i][j] = max(mat[i-1][j-1]+1, mat[i][j])

print(mat[al][bl])

LCS의 규칙대로 문제를 풀면 된다. 이전에서 나온 것 중 최대 중첩의 수를 옮겨와서 이번 차례에서 또 중첩이 된다면 하나를 올려 기록해준다. 이것이 이후의 누적으로 사용된다.

결과

맞았습니다!!

모범답안

출처

word1, word2 = input(),input()
l1, l2 = len(word1), len(word2)
cache = [0] * l2

for i in range(l1):
    cnt = 0
    for j in range(l2):
        if cnt < cache[j]:
            cnt = cache[j]
        elif word1[i] == word2[j]:
            cache[j] = cnt + 1
print(max(cache))

연산시간이 5배나 짧은데 메모리 사용량과 코드량도 짧은 코드가 있어서 분석해보려 한다.

cache를 사용하여 푸는 것 같은데 2중 for문도 돌리고… 어떤 방식으로 푼 건지는 잘 모르겠다.