개발이야기/코딩테스트
[백준-9251(LCS)] LCS
Study & Stack
2025. 6. 11. 15:57
728x90
문제
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-index로 쉽게 접근
- len(str1)+1, len(str2)+1 크기의 2차원 DP 배열 생성
- 이중 for문으로 문자 비교하며 DP 테이블 채움
- 최종 결과는 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])
728x90