문제
해설
두 문자열을 입력 받아 겹치는 부분 수열중 가장 긴 것의 길이를 출력하면 된다. 두 문자열은 알파벳으로만 이루어져 있다. 길이가 같다는 보장은 없는 것 같다.
다이나믹 프로그래밍으로 다음과 같이 풀면 된다.
| | # | C | A | P | C | A | K |
|---|---|---|---|---|---|---|---|
| # | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Y | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| K | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| P | 0 | 0 | 0 | 0 | 0 | 0 | 0 |두 단어의 길이만큼 행과 열을 정하고 2차원 배열을 생성 후 초기값으로 모두 0으로 채워준다.
이 때 각 단어의 앞에 특수문자 '#'을 넣어 줬다. (꼭 #일 필요는 없음)
DP 문제에서 배열을 채울 때는 늘 전 인덱스를 참고하기 때문에 배열의 시작 인덱스에서 배열범위 밖 원소 접근을 방지하기 위해 일부러 여분의 0값을 앞에 채워놓는 경우가 많다. 단어가 알파벳으로만 이루어져 있다는 가정이 있기에 여분의 특수문자를 단어 맨 앞에 붙여주었다.
| | # | C | A | P | C | A | K |
|---|---|---|---|---|---|---|---|
| # | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Y | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| K | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| P | 0 | 0 | 0 | 0 | 0 | 0 | 0 |두번째 행부터 배열을 차례대로 순회한다. 순회하며 숫자를 채워 넣는 공식은 다음과 같다.
해당 행의 알파벳 값(위 상황에선 A)과 열의 알파벳 값(위 상황에선 차례대로 #, C, A, P, C, A, K)이 같을 때 그 자리의 왼쪽 위 대각선 값 + 1을 채워 넣는다.
같지 않은 경우는 MAX(위쪽 값, 왼쪽 값)을 채운다.
이러한 패턴으로 테이블을 채워 넣으면
| | # | 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 문제는 늘 공식이나 패턴을 찾아야 풀 수 있는데 2차원 배열을 써야 하는 DP 문제는 패턴 찾기가 유독 까다로운 것 같다. 그래서 다른 블로그의 해법을 많이 참고하여 풀었다.
코드(Python)
a = '#' + input()
b = '#' + input()
dp = []
row = len(a)
col = len(b)
for i in range(row):
dp.append([0] * col)
for i in range(1, row):
for j in range(col):
if a[i] == b[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
result = 0
for r in dp:
result = max(result, max(r))
print(result)