[TIL][Mon] LCS : DP

 

Reference

누워서 보는 알고리즘: 12. 최장공통부분서열 문제. LCS (Longest Common Subsequence)

https://www.youtube.com/watch?v=z8KVLz9BFIo

16. Dynamic Programming, Part 2: LCS, LIS, Coins

https://www.youtube.com/watch?v=KLBCUx1is2c

최장공통부분서열 Longest Common Subsequence

x : hieroglyphology

y: michelangelo

⇒ hello

두 문자서열(문자열) x와 y에 대하여 두 문자열에 공통으로 나타나는 부분문자서열(subsequence) 중 최대의 길이를 가지는 부분서열을 최장공통부분서열이라고 한다. → 최대, 즉 최적화Optimazation 문제

백준 문제

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

부분서열subsequence vs 하위 문자열substring

영문	subsequence	substring
한국어명	부분서열	하위문자열
정의	원래의 문자열과 같은 순서로 나타나는 문자열의 서열.	문자열에서 문자들의 연속된 서열(contiguous sequence)
예시	Hello 라는 문자열에서 Hlo 는 부분서열이다.	Hello 라는 문자열에서 Hell은 하위문자열이다.
특징	같은 순서로 나타나야 하지만 반드시 연속적이지 않아도 된다.	원래 문자열과 동일한 순서, 연속되어야 함. (떨어지면 안 됨)

Brute-Force approach

x의 모든 부분 서열 중에서 y의 부분 서열인 것들의 길이를 구하고 이 길이들 중에서의 최댓값을 찾는다. 이 경우 x의 모든 부분 서열을 구하는 시간복잡도는 2^m 인데, 왜냐하면 x안의 모든 문자열에 대하여 있다/없다 두 가지 경우의 수를 모두 구해야 하기 때문이다. 따라서 지수 시간 복잡도exponential time compexity를 가진다.

재귀적 접근 : Top Down

#두 문자열 x, y
X = {x1, x2, x3 ... ,x(m-1), x(m)}
Y = {y1, y2, y3 ... ,y(n-1), y(n)}

#두 문자열의 최장공통부분서열을 z, 그 갯수를 k라 가정
z= {z1, z2, z3, ... , z(k-1), z(k)}

#임의의 재귀 함수 LSC를 가정.
def LCS(): 
	...

두 가지 경우로 나뉘어진다.

X(m)=Y(n) 일 때

# 두 문자열의 마지막 글자가 같다면 
# 최장공통부분서열의 마지막 문자도 같을 것이다. 
# 따라서 다음이 성립한다. 

z(k)=X(m)=Y(n)

# z(k) 는 해결했다. 
# 그렇다면 z(k-1)은?

z(k-1)= LCS (X(m-1), Y(n-1))

# z(k) 에 이르기 전까지의 z(k-1)은 
# X의 m-1번째 글자와 Y의 n-1번째 글자 까지의 분량을 가지고 
# LCS 라는 함수에 넣어 반환되는 값이 
# z(k-1)이 될 것이다.  =z(k) 

#그렇다면 이걸 가지고 뭘 하지?
# 3에서 이어짐

X(m) ≠ Y(n) 일 때

#1 : x(m) != y(n) 이고 z(k) != x(m) 일 때 : 
Z= LCS(X(m-1), Y(n))

#2 : x(m) != y(n) 이고 z(k) != y(n) 일 때: 
Z= LCS(X(m), Y(n-1))

재귀적으로 정의하기 (Recurrence Equation)

c(i, j): #수열 X(i)와 Y(j)의 최장공통부분서열의 길이로 정의한다

##### 재귀식 #####

# 종료 조건
i =0  또는 j =0 이면 c( i, j ) =0 이다.  #종료 조건

# 재귀 조건 1
if X(i) = Y(j): 
 c(i,j)=c(i-1, j-1) + 1 # c(i-1, j-1) 까지의 길이에서 +1한다. 

# 재귀 조건 2
if X(i) != Y(j):
	c(i,j) = max( c(i-1, j) , c(i, j-1) )

하향식(Top-down): recursion code

import sys
X = input()
Y = input()

sys.setrecursionlimit(20000)

###### recursion ######
###### 시간 초과 ###### 

def LCS(X, Y):
    m = len(X)
    n = len(Y)

    if m ==0 or n ==0:
        return 0
    else:
        if X[-1]==Y[-1]:
            return LCS(X[:(m-1)], Y[:(n-1)])+1
        
        else:
            return max(
                LCS(X[:m-1], Y[:n]),
                LCS(X[:m], Y[:n-1])
            )
    
print(LCS(X, Y))

상향식 접근 : bottom-up

• 인접행렬로 테이블 (cache)로 바꾸어 값을 저장해두며 접근한다.

import sys
X, Y = [ sys.stdin.readline().strip() for _ in range(2)]

def LCS(X,Y):
    X, Y = ' '+X, ' '+Y # 편의를 위한 장치 
    m,n = len(X), len(Y)
    c=[[0 for _ in range(n)] for _ in range(m)] # Y, X
    
    
    for i in range(1, m):
        for j in range(1, n):
            if X[i] == Y[j]:
                c[i][j]=c[i-1][j-1]+1
            else:
                c[i][j]=max(c[i-1][j], c[i][j-1])
                
    
    return c[-1][-1] 

print(LCS(X,Y))

왜 상향식 접근이 더 빠를까?

하향식 접근(재귀)의 경우에는 불필요한 값이어도 되짚어 재귀적으로 풀어가려면 함수를 호출하지만 상향식 접근(for loop)는 불필요한 함수 호출이 적어서 cache hit rate가 높다.