3304_최장 공통 부분 수열

SWEAD3_3304최장 공통 부분 수열

문제

주어진 두 문자열의 최대 공통 부분 수열(Longest Common Sequence)의 길이를 계산하는 프로그램을 작성하시오.

예를 들어 "acaykp"와 "capcak"의 경우, 두 문자열의 최대 공통 부분 수열은 "acak"로 길이가 4이다.

최장 공통 부분문자열(Longest Common Substring)을 계산하는 것이 아님에 주의한다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 두 문자열이 공백을 사이에 두고 주어진다.

각 문자열은 알파벳 소문자로만 구성되어 있음이 보장된다.

각 문자열의 길이는 1,000 이하의 자연수이다.

[출력]

각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 공통 부분 수열의 길이를 출력한다.

입력

1

acaykp capcak

출력

#1 4

설명

이 문제는 LCS(Longest Common Subsequence) 알고리즘을 사용해서 해결할 수 있다.

먼저 제귀적으로 풀어내는 방법으로 시작해보면

A = acaykp

B=capcak

입력받은 두 문자열을 넘겨받는 lcs1함수를 구현한다.

넘겨받은 문자열의 길이가 0 이라면 바로 0을 리턴하고

아니면 공통 부분 수열을 확인한다.

점화식

문자열의 마지막 문자가 같은지 다른지를 비교해서

1. 같은 문자라면 리턴에 += 1 값을 증가시킬 것이다.
2. 다르면 두 문자열 중에서 하나를 제거하고 재귀호출한다.

def lcs1(x, y):
    m, n = len(x), len(y)
    if m == 0 or n == 0:
        return 0
    else:
        if x[-1] == y[-1]:
            return lcs1(x[: (m - 1)], y[: (n - 1)]) + 1
        else:
            return max(lcs1(x, y[: (n - 1)]), lcs1(x[: (m - 1)], y))

for case in range(1, 1 + int(input())):
    A, B = input().split()
    print(lcs1(A, B)) # 4

코드로 표현하면 이렇게된다.

이런 식으로 풀이한다면 재귀호출의 호출 횟수는 최대 O(2^n)이며

문자열의 길이에 비례해 시간이 급격히 오래 걸릴 수 있다.

다음 방법은 dp 풀이 방법이다.

1. dp를 저장할 2차원 배열을 생성한다.
2. 문자열의 각 자리를 순회하면서 같은 값이 있다면 전에 값에 +=1 하는 식이다.
   1. 여기서 전에 값 방향은 대각선 왼쪽이다.
3. 값이 다르면 전에 기록한 값 중 큰 값을 가져온다.
   1. 기록된 값은 왼쪽, 위쪽이다.
4. 마지막 위치를 출력하면 찾던 답이다.

def lcs2(x, y):
    x, y = " " + x, " " + y
    m, n = len(x), len(y)
    dp = [[0] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            if x[i] == y[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
  # 마지막 위치의 값이 답  
	return dp[m - 1][n - 1]

for case in range(1, 1 + int(input())):
    A, B = input().split()
    print(f"#{case}", end=" ") # #1
    print(lcs2(A, B)) # 4

dp 결과

    a c a y k p
  0 0 0 0 0 0 0 
c 0 0 1 1 1 1 1 
a 0 1 1 1 2 2 2 
p 0 1 2 2 2 3 3 
c 0 1 2 2 2 3 3 
a 0 1 2 2 2 3 4 
k 0 1 2 3 3 3 4

dp 결과

여기까지만 해도 답은 충분히 구할 수 있다.

하지만 마지막으로 그 결과가 무엇인지(어떤문자로구성된건지) 구하는 방법까지 알아보자.

방법

dp와 같은 배열은 하나 더 생성한다.

dp가 기록될 때 어떤 방향의 값을 가져온 것인지를 기록한다면

그 경로를 저장하는 격이 된다.

그리고 두 문자열이 같은 경우를 1로 저장했으니까

경로를 따라 가면서 1이 있으면 그 문자를 문자열에 더해준다면

공통 부분 수열 값을 구할 수 있다.

def lcs3(x, y):
    x, y = " " + x, " " + y
    m, n = len(x), len(y)
    dp = [[0] * n for _ in range(m)]  # 공통부분수열 기록
    way = [[0] * n for _ in range(m)]  # 최적의 해를 찾는 경로 저장.

    for i in range(1, m):
        for j in range(1, n):
            if x[i] == y[j]:  # 각 자리의 값이 같다면
                dp[i][j] = dp[i - 1][j - 1] + 1  # 대각선 위 값에 1더한 값
                way[i][j] = 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                # 어느 것이 큰지 비교해서 어떤 위치의 값이 선택된 것인지 기록한다.
                way[i][j] = 2 if (dp[i - 1][j] < dp[i][j - 1]) else 3
    return dp, way

def get_way(i, j, b, x):
    if i == 0 or j == 0:
        return ""
    else:
        if b[i][j] == 1:
            return get_way(i - 1, j - 1, b, x) + x[i]
        elif b[i][j] == 2:
            return get_way(i, j - 1, b, x)
        elif b[i][j] == 3:
            return get_way(i - 1, j, b, x)

for case in range(1, 1 + int(input())):
    A, B = input().split()
    dp, way = lcs3(A, B)

    print_matrix(way)
    print(get_way(len(A), len(B), way, " " + A)) # acak

way 결과