LCS (골드5)

# 문제

문제

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

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

입력

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

출력

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

 

# 나의 풀이

 

 - 접근

 

먼저 완전탐색으로 접근하였지만, 방법이 생각나지 않았다. 

 

유튜브 강의를 통해 학습하였다. 

 

bottom - up 방식으로 2차원 dp 테이블을 채워나가는 것이 핵심이다.

 

여기서 처음으로 배운 것

 

1. 부분 문자열을 다른 표현방식으로 치환

2. dp table을 구할 때 다양한 조건식 사용

3. 2차원 dp 테이블을 활용할 것

4. 초기값 0을 dp 테이블을 선언 시 초기화 한것

 

 

# 최종 제출 코드

# 최장 공통 부분 수열(LCS) 10월6일 복습

import sys

read = sys.stdin.readline

# 입출력 시간 개선

string1, string2 = read().strip(), read().strip()

X = len(string1) + 1

Y = len(string2) + 1

dp = [[0] * Y for _ in range(X)] # dp 테이블 초기화

for y in range(1, Y):

    for x in range(1, X):

        if string1[y-1] == string2[x-1]:

            dp[y][x] = dp[y-1][x-1] + 1

        else:

            dp[y][x] = max(dp[y][x-1], dp[y-1][x])

print(dp[-1][-1])

 

더 배울 것

 

부분 문자열의 길이가 뿐 아닌 그 문자열을 찾는 방식 학습

 

인덱스 경계값 철저히 확인하기