[정글 알고리즘] - [중] 백준9251- LCS- 골드5

 

코드 한 줄 설명과 DP 테이블 변화에 집중한 상세형 정리다.

1. 문제를 아주 짧게 말하면

두 문자열이 주어졌을 때, 두 문자열에 모두 등장하는 공통 부분 수열 중 가장 긴 것의 길이를 구하는 문제다.

예를 들어 ACAYKP 와 CAPCAK 의 LCS는 ACAK 이고 길이는 4다. [Source](https://www.acmicpc.net/problem/9251)

2. 핵심 아이디어

dp[i][j]의 뜻

첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자를 봤을 때 만들 수 있는 LCS의 최대 길이

• 문자가 같으면 dp[i][j] = dp[i-1][j-1] + 1
• 문자가 다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 전체 코드

1import sys

2

3s1 = sys.stdin.readline().strip()

4s2 = sys.stdin.readline().strip()

5

6n = len(s1)

7m = len(s2)

8

9dp = [[0] * (m + 1) for _ in range(n + 1)]

10

11for i in range(1, n + 1):

12 for j in range(1, m + 1):

13 if s1[i - 1] == s2[j - 1]:

14 dp[i][j] = dp[i - 1][j - 1] + 1

15 else:

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

17

18print(dp[n][m])

4. 코드 한 줄씩 설명

줄	코드	설명
1	import sys	빠른 입력을 위해 sys 모듈을 가져온다.
3	s1 = sys.stdin.readline().strip()	첫 번째 문자열을 입력받고 줄바꿈을 제거한다.
4	s2 = sys.stdin.readline().strip()	두 번째 문자열도 같은 방식으로 입력받는다.
6	n = len(s1)	첫 번째 문자열 길이를 저장한다.
7	m = len(s2)	두 번째 문자열 길이를 저장한다.
9	dp = [[0] * (m + 1) for _ in range(n + 1)]	(n+1) x (m+1) DP 테이블을 만든다. 0행, 0열은 빈 문자열과 비교한 경우다.
11	for i in range(1, n + 1):	첫 번째 문자열을 앞에서부터 한 글자씩 반영한다.
12	for j in range(1, m + 1):	현재 i번째 문자와 두 번째 문자열의 j번째 문자를 비교한다.
13	if s1[i - 1] == s2[j - 1]:	두 문자가 같은지 확인한다. 문자열 인덱스는 0부터라서 i-1, j-1을 쓴다.
14	dp[i][j] = dp[i - 1][j - 1] + 1	같다면 공통 부분 수열 길이를 1 늘릴 수 있으므로 대각선 왼쪽 위 값에 1을 더한다.
15	else:	문자가 다르면 둘을 동시에 사용할 수 없으므로 다른 경우를 비교한다.
16	dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])	위쪽과 왼쪽 중 더 큰 값을 가져와 현재 위치의 최적값으로 둔다.
18	print(dp[n][m])	마지막 칸이 두 문자열 전체를 비교한 LCS 길이이므로 출력한다.

5. DP 테이블 시각화

예시 문자열 ACAYKP, CAPCAK 기준으로 채운 표다. 초록색은 현재 문자가 같은 위치다.

s1 \ s2	∅	C	A	P	C	A	K
∅	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

마지막 칸 dp[6][6] = 4 가 정답이다.

6. 행이 채워질 때마다 어떻게 바뀌는지

각 행은 첫 번째 문자열에서 문자를 하나 더 반영했다는 뜻이다.

i=1, 현재 문자 'A'를 반영한 뒤

dp[1] = [0, 0, 1, 1, 1, 1, 1]

i=2, 현재 문자 'C'를 반영한 뒤

dp[2] = [0, 1, 1, 1, 2, 2, 2]

i=3, 현재 문자 'A'를 반영한 뒤

dp[3] = [0, 1, 2, 2, 2, 3, 3]

i=4, 현재 문자 'Y'를 반영한 뒤

dp[4] = [0, 1, 2, 2, 2, 3, 3]

i=5, 현재 문자 'K'를 반영한 뒤

dp[5] = [0, 1, 2, 2, 2, 3, 4]

i=6, 현재 문자 'P'를 반영한 뒤

dp[6] = [0, 1, 2, 3, 3, 3, 4]

7. 중요한 칸 직접 따라가기

dp[1][2] 계산

비교 문자: 'A' vs 'A'

문자 'A'와 'A'가 같아서 대각선 값 dp[0][1]=0에 1을 더해 1가 된다.

dp[2][1] 계산

비교 문자: 'C' vs 'C'

문자 'C'와 'C'가 같아서 대각선 값 dp[1][0]=0에 1을 더해 1가 된다.

dp[3][5] 계산

비교 문자: 'A' vs 'A'

문자 'A'와 'A'가 같아서 대각선 값 dp[2][4]=2에 1을 더해 3가 된다.

dp[5][6] 계산

비교 문자: 'K' vs 'K'

문자 'K'와 'K'가 같아서 대각선 값 dp[4][5]=3에 1을 더해 4가 된다.

dp[6][4] 계산

비교 문자: 'P' vs 'C'

문자가 다르므로 위 dp[5][4]=2와 왼쪽 dp[6][3]=3 중 큰 값 3를 가져온다.

8. 자주 헷갈리는 포인트

• 부분 수열은 연속할 필요가 없다.
• 문자가 다를 때 대각선이 아니라 위/왼쪽 중 큰 값을 가져온다.
• 이 문제는 실제 문자열이 아니라 길이를 출력한다.

9. 복잡도

모든 칸을 한 번씩 채우므로 시간 복잡도는 O(NM) 이다.

DP 테이블 전체를 저장하므로 공간 복잡도도 O(NM) 이다.

원문 문제 링크

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