[백준-9251(LCS)] LCS

 

문제바로가기

 

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

ACAYKP
CAPCAK

예제 출력

4

 

---

문제 핵심 아이디어

두 문자열의 부분 수열 중 가장 긴 공통 부분 수열의 길이를 구하라.

• 부분 수열: 연속될 필요는 없지만 순서는 지켜야 함
• 문자 하나하나를 비교하며 공통되는 문자를 이어가되, 공통되지 않으면 최선의 선택을 누적한다

해결 전략 - 동적 계획법 (DP)

1. DP 정의

• dp[i][j] = str1[1..i]와 str2[1..j]의 LCS 길이

2. 점화식

if str1[i] == str2[j]:
    dp[i][j] = dp[i-1][j-1] + 1  # 문자가 같으면 대각선 + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 다르면 왼쪽 or 위쪽 중 큰 값

초기 조건

• dp[0][*] = dp[*][0] = 0 → 공백 문자열은 공통 부분 수열이 없음

접근 방법 정리

1. 두 문자열에 ' '를 앞에 추가해 1-index로 쉽게 접근
2. len(str1)+1, len(str2)+1 크기의 2차원 DP 배열 생성
3. 이중 for문으로 문자 비교하며 DP 테이블 채움
4. 최종 결과는 dp[-1][-1] 또는 dp[len(str1)-1][len(str2)-1]

import sys
input = sys.stdin.readline

# 공백을 앞에 추가해 인덱스를 1부터 시작할 수 있게 함
str1 = ' ' + input().strip()
str2 = ' ' + input().strip()

# DP 테이블 초기화: 행은 str1 기준, 열은 str2 기준
# dp[i][j]는 str1의 i번째 문자까지와 str2의 j번째 문자까지의 LCS 길이
dp = [[0] * (len(str2)) for _ in range(len(str1))]

# DP 테이블을 채움
for i in range(1, len(str1)) :                  # str1의 각 문자(1부터) 순회 (행)
    for j in range(1, len(str2)) :              # str2의 각 문자(1부터) 순회 (열)
        if str1[i] == str2[j] :                 # 현재 문자가 같다면
            dp[i][j] = dp[i-1][j-1] + 1         # 대각선 왼쪽 위의 값 + 1
        else :  
            # 문자가 다르면 왼쪽(dp[i][j-1]) 또는 위쪽(dp[i-1][j]) 중 큰 값 선택
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

# 최종 LCS 길이는 DP 테이블의 오른쪽 아래 값
print(dp[-1][-1])