백준 9251 풀이 (LCS, 다이나믹 프로그래밍)

LCS는 Longest Common Subsequence라고 한다. 최장 공통 부분 수열.....이름부터 먼가 심상치 않다.

두 수열이 주어질때 공통으로 가장 긴 부분 수열을 찾는 알고리즘이다.

C와 ACAYKP를 비교한다고 생각하고 2차원 배열을 만든다.

이후에 CA, CAP, CAPC....등으로 확장해나간다.

그러면 아래와 같은 2차원 배열이 생성된다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

이때 확인 할 수 있는 것은 다음과 같다.(파랑색은 증가한 경우, 빨강색은 알파벳이 같아도 증가하지 않는경우)

1. 알파벳이 서로 같아질때 왼쪽 위 대각선 값에서 1을 증가시킨 값을 상속받는다.

2. 알파벳이 서로 다를 경우 왼쪽값과 위쪽 값중 큰 값을 상속받는다.

 

이를 토대로 코드를 작성 하면 아래와 같다.

a = input()
b = input()

dp = [[0 for i in range(len(a)+1)] for k in range(len(b)+1)]
for j in range(1,len(b)+1):
    for i in range(1,len(a)+1):
        if b[j-1] == a[i-1]:
            dp[j][i] = dp[j-1][i-1] + 1
        else:
            dp[j][i] = max(dp[j][i-1], dp[j-1][i]) 
print(max(dp[-1]))

 

내 설명은 썩 좋다고 생각되지 않아서 좋은 글이 있으니 아래를 통해 추가 자료를 공부하면 좋을거 같다.

twinw.tistory.com/126