[백준] - 다이나믹 프로그래밍 LCS

LCS  

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.1 초 (하단 참고)

256 MB

56865

23037

16944

40.292%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

출처

---

Knapsack 문제이다. 

ACAYKP

CAPCAK

 

이와같이 연속되지 않은 경우 어떻게 해야 겹치는 개수를 카운트 할 수 있을까? 

 

바로 전 문제에서 다뤘던 것과 동일한 방법이다. 

연속적이지 않은 누적 합을 구할 때 항상 이 방법을 떠올리면 된다. 

 

https://myjamong.tistory.com/317

백준 9251 파이썬 - LCS - 동적 계획법

겹친 순간 부터 뒤 까지 모두 겹친 수를 반영해준다. 이로써 추후 업데이트가 가능하다. 

추가적으로 이 문제의 경우 밑에서 올라오는 수가 기존 값을 넘어설 수 있으므로 

그전 값에서 업데이트 되는 값과 이번에 새롭게 올라온 값의 비교를 해주어야 한다. 

 

A = input().rstrip()
B = input().rstrip()

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


for i in range(1, a+1):
    for j in range(1, 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)
print(dp[len(A)][len(B)])

그리고 항상 캐시를 초기화 할 때 크기를 N 에 맞춰서 하고 싶은 마음이 있는데, 이 경우 index 0 이전 즉, 오히려 최종 index 에 접근하게 된 경우 예상치 못한 값을 반영할 수 있기 때문에 유의해줘야한다.

 

다만 이 문제에서는

https://itforfun.tistory.com/231 

[백준] 다이나믹 프로그래밍 - 평범한 가방

이 문제에서는 할 수 없었던 배열 1개 이용하여 업데이트가 가능하다. 

여기서는 단어가 겹치는 경우에 무조건 cnt 가 더 업데이트 되어 있기 때문이다. 

import sys
read = sys.stdin.readline

word1, word2 = read().strip(), read().strip()
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))

다만 시간 차이는 별로 없고, 이 경우는 모든 경우에 적용 가능한 것이 아니므로 1번을 더 잘 알고 있는 것이 좋은 것 같다. 

 

 

---

추후 유사문제를 풀려 하는데 알고리즘이 떠오르지 않았다. 

이는 저번에 풀 때 완벽하게 이해하지 못하고 풀어서 인 듯 하다. 

 

해당 문제 알고리즘을 다시 한번 정리해보자면, 

 

ACAYKP

CAPCAK

 

ACAYKP

CAPCAK

...

 

 

ACAYKP

CAPCAK

한칸씩 돈다. 

 

한칸씩 돌 때 다음의 조건을 만족한다.

 

• 현재 가장 길게 유지되고 있는 길이가 몇인지 확인할 수 있어야 한다.  
• 새롭게 일치하게 되면 그전까지 index의 값들보다 1이 커진다. 
• 새롭게 일치해지면 당연히 그 이후 index의 값들도 앞선 index 의 크기가 커진만큼 커져야 한다.

LCS 2 

계산식을 역으로 해야한다.