[백준] 9251 - LCS

1. 문제 요약

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

두 문자열이 주어졌을 때,
공통 부분 수열 중 가장 긴 길이(LCS) 를 구하는 문제이다.

예시:

A = ACAYKP
B = CAPCAK

 

→ LCS: ACAK (길이 4)

---

2. 처음 접근: 브루트포스

처음에는 단순하게 생각했다.

"부분수열을 전부 만들어서 공통된 것 중 가장 긴 걸 찾으면 되지 않을까?"

그래서 이렇게 구현했다:

from itertools import combinations

a_commons = []
b_commons = []

# a의 모든 부분수열 생성
for i in range(1, len(a) + 1):
    for comb in combinations(a, i):
    	a_commons.append(''.join(comb))

# b의 모든 부분수열 생성
for i in range(1, len(b) + 1):
    for comb in combinations(b, i):
    	b_commons.append(''.join(comb))

 

그리고 공통된 문자열을 찾으려고 했다.

---

3. 문제점 1: 코드 버그

처음에는 아래 코드 때문에 결과가 1이 나왔다.

 

if a_common in b_common:

 

여기서 b_common은 리스트가 아니라 마지막 문자열 하나였다.

👉 즉, 전체가 아니라 "K" 같은 문자열 하나만 비교하고 있었던 것.

✔ 해결

 

if a_common in b_commons:

 

---

4. 문제점 2: 시간 복잡도

근본적인 문제는 따로 있었다.

부분수열 개수는 다음과 같다:

길이 n → 부분수열 개수 ≈ 2^n

 

문제 조건:

n ≤ 1000

 

👉 2^1000 → 절대 불가능

---

5. 깨달음: “전체를 만들지 말고, 부분 문제만 보자”

브루트포스는

모든 부분수열을 직접 생성

하지만 DP는

앞에서부터 잘라서 만든 최적해만 저장

---

6. DP 접근

정의

 

dp[i][j] = a[:i]와 b[:j]의 LCS 길이

 

즉,

• i는 a의 길이
• j는 b의 길이

---

7. 점화식

 1) 문자가 같을 때

if a[i-1] == b[j-1]:
	dp[i][j] = dp[i-1][j-1] + 1

 

👉 공통 부분수열에 포함 가능

---

 2) 문자가 다를 때

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

 

👉 둘 중 하나는 버려야 함

---

8. 최종 코드

import sys
input = sys.stdin.readline

a = input().rstrip()
b = input().rstrip()

an = len(a)
bn = len(b)

dp = [[0] * (bn + 1) for _ in range(an + 1)]

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

print(dp[an][bn])

 

---

⏱ 시간 복잡도 비교

방법시간 복잡도

브루트포스	O(2^n) ❌
DP	O(n × m) ✅