[python] 백준 - 9251. LCS

🤔문제 해결

G5 | 다이나믹프로그래밍, 문자열

 

LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다.

순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다.

예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다.

 

LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 

문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다.

먼저 위와 같이 DP를 구성한다.

 

먼저 1번 째 행을 채워보면

• AC와 C가 만나서 LCS는 1이다.

두번 째 행을 보자.

• A와 CA가 만나서 LCS는 1이다.
• ACA와 CA가 만나서 LCS는 2이다.

 

세번 째 행을 보자.

• A와 CAP = 1
• ACA와 CAP = 2
• ACAYKP와 CAP = 3

여기서 두가지 규칙을 확인해야 한다.

• 문자가 같을 경우: 이전 문자까지의 LCS + 1
  EX) ACAYKP와 CAP를 봤을 때 P가 같은 문자이다.
  그렇다면 ACAYK 와 CA 의 LCS 는 2이고 +1을 해주게 되면
  ACAYKP와 CAP 의 LCS 는 3이 된다.
• 문자가 다를 경우: 두 단어에서 각각의 이전단계의 LCS 중 큰 값
  EX) ACA와 CAP 에서 A 와 P가 다르므로 이전의 값 LCS
  1. AC와 CAP = 1
  2. ACA와 CA = 2
  이 둘 중 max값을 넣는다.

이렇게 마지막까지 가게 된다면 아래와 같은 결과를 얻을 수 있다. dp의 마지막 값을 출력하면 된다.

 

💨 !심화 학습 : 이제 LCS의 구성 문자를 구해보자.

DP의 가장 아래에서 부터 각 행의 가장 큰값중 앞쪽에 있는 값을 선택해준다. 
( 하지만 각 행과 열은 하나의 값만 존재해야 한다.

이렇게 우리는 ACAK를 얻을 수 있다.

💻소스 코드

def solution(a, b):
    a = ' ' + a
    b = ' ' + b
    an = len(a)
    bn = len(b)

    dp = [[0]*an for _ in range(bn)]
    for i in range(1, bn):
        for j in range(1, an):
            if b[i] == a[j]:
                dp[i][j] = dp[i-1][j-1] + 1

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

        for row in dp:
            print(row)
        print()
    print(dp[-1][-1])
    return


if __name__ == "__main__":
    a0 = input()
    b0 = input()
    solution(a0, b0)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

9251번: LCS

---

문제

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

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

입력

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

출력

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