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

백준 9251 파이썬

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

9251번: LCS

이번 문제는 두개의 문자열이 주어졌을 때 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 구하는 문제다.

예를 들어 

ACAYKP

CAPCAK

LCS는 ACAK 이다.

 

이전에 풀었던 동적 계획법이랑은 조금 다르게 2차원 배열의 캐시를 만들어서 해결할 수 있고... 누적 값을 구해서 해결할 수도 있다.

 

 

Python 풀이 1

해당 풀이는 2차원 배열을 사용한 동적 계획법이다.

2차원 배열의 캐시값을 만들어 동적 계획법으로 풀때는 2개의 문자열의 현재 시점에서 LCS 값을 구하는 원리다. 배열을 채우기 위해 문자열의 알파벳을 순회할때... 만약 같은 알파벳인 경우 해당 위치에서는 글자를 추가하기 전의 LCS 값보다 1을 더해서 저장한다. 이중 for문으로 i, j를 사용했을 때 위치가 [i-1][j-1]의 위치이다. 만약 알파벳이 다른 경우... 이전까지 비교한 값중 최대값을 구해야한다. 예를 들어...  CAP와 ACA를 비교할때 마지막 글자인 P와 A는 서로 다르다. 그래서 이전까지 구한 값... CAP, AC = 1 그리고 CA, ACA = 2 두가지 경우가 생긴다. 이중 최대값이 CAP와 ACA까지의 LCS가 될것이다.

 

import sys
read = sys.stdin.readline

word1, word2 = read().strip(), read().strip()
h, w = len(word1), len(word2)
cache = [[0] * (w+1) for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if word1[i-1] == word2[j-1]:
            cache[i][j] = cache[i-1][j-1] + 1
        else:
            cache[i][j] = max(cache[i][j-1], cache[i-1][j])
print(cache[-1][-1])

• 이전 값을 갖고 하기 때문에 글자의 크기보다 1나씩 크게 cache배열을 지정한다.
• 글자가 같은 경우 이전 값에서 1을 더하고 글자가 다른 경우 2가지 경우의 수에서 최대값을 저장한다.
• 최종적으로 배열의 마지막 값이 답이 된다.

주의해야할 것이 있다면... 각각 글자의 크기가 다르기 때문에 글자의 index를 올바르게 지정해줘야한다.

 

 

Python 풀이 2

두번 째 풀이도 동적 계획법이고 2중 for문을 사용해야하는 것은 같다. 그러나 cache를 1차원 배열로 지정할 수 있어 풀이 1에서 2차원 배열을 순회하는데 들어가는 시간을 줄일 수 있다. 메모리도 절약되고 시간도 대략 2.5배정도 개선한 결과를 얻었다.

 

글자 하나를 기준으로 1차원 배열을 만들어주고 같은 글자를 순회하는 경우 누적 값에서 1을 더한 값을 넣어주는 방식이다. 순회할 때마다 누적값을 저장할 변수를 하나 사용하고 만약 글자가 다른 경우 누적 변수의 값이 해당 위치의 값보다 작은 경우 해당 값으로 교체해준다. 이렇게 하면 누적 값에는 이전 위치까지 까지의 최대값이 계속해서 저장된다.

 

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))

• cnt를 누적 변수로 사용한다.
• 누적 변수의 값이 캐시값보다 작으면 교체한다.
• 글자가 같은 경우 누적 변수에서 1을 더한다.

주의해야할 사항은... 누적변수의 값이 해당 위치의 캐시값보다 작은지 여부부터 확인해야한다.

XXXXXF

XFXXXQ

반례로 이 두 문자열을 예시로 했을때 만약 글자가 같은지를 먼저 비교해버리면... 누적 값이 추가 되지 않는다.