LCS problem

LCS 문제

DP(Dynamic Programming)의 대표적인 문제 LCS(Longest Common Subsequence) 최장 부분 수열 문제이다.

문제 해결

1. 우선 작은 문제들로 나누고 이에 대한 답을 활용하여 전체적인 답을 구하기 위해서 재귀적인 방법으로 접근해야한다. 첫 번째로 두 개의 경우로 나누어본다.

• Case 1. 문자가 같을 경우(Xi = Yj) 다음 문자를 비교하기 위해 i-1, j-1로 이동해야한다.

• Case 2. 문자가 다를 경우(Xi =! Yj) 어떤 문장의 인덱스를 앞으로 이동할 것인지 결정한다. 즉 (i-1, j), (i, j-1)의 경우로 나뉜다.

1. 정리하면 만약 문자가 같을 경우(Xi = Yj)에는 LCS(X[1~i-1], Y[1~j-1]) + 1을 반환하고 문자가 다를 경우(Xi =! yj)에는 max(LCS(X[1~i-1], Y[1~j]), LCS(X[1~i], LCS[1~j-1]))을 반환한다.

2. 이를 중복 계산되는 문제를 완화하기 위해서 DP 방법으로 전환한다. 2차원 배열을 생성하여 문자가 같을 경우 C[i][j] = C[i-1][j-1]+1, 다를 경우 C[i][j] = max(c[i-1][j], c[i][j-1])을 저장한다

3. 마지막으로 해당되는 문자열들을 출력하기 위해서 새로운 2차원 배열을 생성하여 문자가 같을 경우 2차원 배열 상 대각선 아래로 이동하였기 때문에 1, 다를 경우 값 비교를 통해 왼쪽(c[i][j-1])에서 이동하였다면 2, 나머지 경우(같거나 c[i-1][j]가 큰 경우) 위에서 아래로 값이 내려오기 때문에 3을 입력한다. 이렇게 되면 마지막 배열 값에서 부터 차례로 거슬러 올라가면서 1이 입력된 자리에 해당하는 문자열을 출력하면 끝이난다.

완성 코드

def LCS(x, y):
    x, y = [' '] + x, [' '] + y
    m, n = len(x), len(y)
    c = [[0 for _ in range(n)] for _ in range(m)]
    b = [[0 for _ in range(n)] for _ in range(m)]
    
    # LCS 길이 및 방향 배열 채우기
    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
                b[i][j] = 1  # 대각선 방향
            else:
                if c[i][j-1] > c[i-1][j]:
                    c[i][j] = c[i][j-1]
                    b[i][j] = 2  # 왼쪽 방향
                else:
                    c[i][j] = c[i-1][j]
                    b[i][j] = 3  # 위쪽 방향

    # LCS 길이 저장
    lcs_length = c[m-1][n-1]

    # LCS 문자열 추출
    sa = []
    i, j = m - 1, n - 1
    while i > 0 and j > 0:
        if b[i][j] == 1:  # 대각선으로 이동 (LCS에 포함되는 문자)
            sa.append(x[i])
            i -= 1
            j -= 1
        elif b[i][j] == 2:  # 왼쪽으로 이동
            j -= 1
        else:  # 위쪽으로 이동
            i -= 1

    # 역순으로 쌓였으므로 뒤집어주기
    sa.reverse()

    return lcs_length, ''.join(sa)

y, x = 'HEROICALLY', 'SCHOLARLY'
x, y = list(x), list(y)

lcs_length, lcs = LCS(x, y)

result = f"{lcs} {lcs_length}"

print(result)

HOLLY 5