[swea 3304-파이썬]최장 공통 부분 수열

swea 3304 최장 공통 부분 수열

사용언어 : PYTHON

풀이

우선 최적해(최댓값)을 구하는 문제이기 때문에 다이나믹 프로그래밍을 사용하여 풀 수 있다.

순환식(점화식)을 세울때는 “최적해의 일부분이 그 부분의 최적해” 를 생각해야 한다.

이 문제 같은 경우는 두 문자열의 마지막 문자가 같은 경우와 다른 경우를 생각하여 순환식을 세워야 한다.

(DP(i,j)에서 i와 j는 문자열 X와 Y의 1…i, 1…j 번째까지의 문자열)

(1) 두 문자열의 마지막 문자가 같은 경우

예를들어 CDABE와 CDE라고 가정해보면 마지막 문자 E가 같다.

E는 최장 공통 부분수열에 반드시 포함된다.

따라서 최장 공통 부분수열의 길이는 두 문자열의 마지막 문자 E를 제거한 후 찾은 최장 공통 부분수열의 길이 + 1이 된다.

식으로 나타내면 DP(i,j)=DP(i-1,j-1)+1이 된다.

(2) 두 문자열의 마지막 문자가 다른 경우

CDAB…E와 CDEG…T의 경우

E와 T가 다르므로 두 가지 경우를 생각해볼 수 있다.

최장 공통 부분수열이 E로 끝나는 경우 : T는 최장 공통 부분수열이 될 수 없으므로 DP(i,j)=DP(i,j-1)이다.

최장 공통 부분수열이 T로 끝나는 경우 : E는 최장 공통 부분수열이 될 수 없으므로 DP(i,j)=DP(i-1,j)이다.

둘 중 더 큰 DP가 DP(i,j)가 된다.

즉 DP(i,j)=max(DP(i,j-1),DP(i-1,j)) 이다.

따라서 점화식은 다음과 같이 작성할 수 있다.

위 점화식을 바탕으로 2차원 배열을 생성한 뒤 행방향으로 값을 계산해 나가면 된다.

코드

def dp():

    for p in range(1,len(answer)):
        for q in range(1,len(answer[0])):
            if st[0][p-1]==st[1][q-1]:
                answer[p][q]=answer[p-1][q-1]+1
            else:
                answer[p][q]=max(answer[p-1][q],answer[p][q-1])
    return

T=int(input())

for i in range(T):
    st=list(input().split())
    answer=[[0]*(len(st[1])+1) for _ in range(len(st[0])+1)]
    dp()
    print('#{} {}'.format((i+1),answer[-1][-1]))
    

풀이를 참고하였다.