백준 : LCS(9251) with 파이썬

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

9251번: LCS

문제

LCS

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.1 초 (하단 참고)

256 MB

74123

30211

22201

40.305%

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

문제풀이

이 문제를 이해하기 위해서 가장 빠른 방법은 그냥 입출력값을 분석해보는 것이기에 바로 수행해보았다.

입력값으로 LCS의 길이가 어떻게 출력되는지 확인하기 위해 표로 만들어보았다.

점화식을 어떻게 구하는지 알아냈으니 바로 코드를 보면서 설명하겠다.

n1 = input()

n2 = input()

dp = [[0 for _ in range(1001)] for _ in range(1001)]

for i in range(1, len(n2) + 1):

      for j in range(1, len(n1) + 1):

            if n1[j - 1] == n2[i - 1]:

               dp[i][j] = dp[i - 1][j - 1] + 1

               continue

            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(max(sum(dp, [])))

------------------------------------------------------------------------------------------------------------

n1 = input()

n2 = input()

n1, n2에 각각 행과 열에 집어 넣을 값을 입력받습니다.

dp = [[0 for _ in range(1001)] for _ in range(1001)]

dp에 n1, n2를 위에서 만든 표처럼 구현하기 위한 반복문입니다. 여기까지 출력을해보면

print(dp)

-> [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]

이런식으로 빈 배열이 생성되는 것을 볼 수 있습니다.

for i in range(1, len(n2) + 1):

      for j in range(1, len(n1) + 1):

            if n1[j - 1] == n2[i - 1]:

               dp[i][j] = dp[i - 1][j - 1] + 1

               continue

            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

우선 i, j를 반복문을 사용해서 빈배열을 채워줍니다. 

그리고 if 조건문을 활용해서 n2, n1의 비교값이 같을 경우 대각선 위의 값에 1을 더한 값을 저장합니다. (LCS 길이 증가)

만약  현재 문자가 다르다면 이전 값 중 큰 값 선택합니다. (LCS 길이 유지) 위에서 구했던 점화식입니다.

print(max(sum(dp, [])))

최종적으로 dp의 sum()함수를 사용해서 합을 구하고 max()함수를 사용하여 최댓값을 구하면 입력받은 배열에 LCS길이를 구할 수 있게 됩니다.