✔ 풀이를 위한 아이디어
- 다이나믹 프로그래밍 (Dynamic Programming)
- LCS (Longest Common Subsequence, 최장 공통 부분 수열) 문제
✔ 알고리즘 설명
이 문제는 배낭 문제와 마찬가지로, 2차원 배열로 푸는 DP 문제이다. 복습하도록 하자.
-
( len(string A) + 1 ) X ( len(string B) + 1 ) 사이즈의 2차원 배열을 선언하고, default 값은 모두 0으로 채워넣는다.
-
두 String을 구성하고 있는 각 요소들을 윗 줄부터 하나씩 비교해나가면서, 서로 값이 일치하는지 판단한다.
-
만약 값이 일치할 경우 (그림에서 민트색), 대각선 방향 왼쪽 위에 있는 값에 1을 더해서 현재 값에 넣어준다. 이는 지금까지의 최대 공통 부분수열에 1을 더해주는 것을 의미한다.
LCS [ i ][ j ] = LCS [ i - 1 ][ j - 1 ] + 1
-
만약 값이 일치하지 않을 경우 (그림에서 파란색), 이전 과정까지의 최댓값을 현재 값에 넣어준다. 부분 수열은 연속된 값이 아니므로, 이전 과정까지의 최대 공통 부분수열은 계속해서 유지되기 때문이다. 이때, 이전 과정이라 함은 표에서 바로 인접한 왼쪽 방향의 값과 위쪽 방향의 값을 의미한다.
LCS[ i ][ j ] = max ( LCS [ i ][ j - 1 ], LCS[ i - 1 ][ j ] )
-
두 String의 모든 요소들을 비교했을 때의 최댓값은 표의 오른쪽 아래 (가장 끝 값) 에 담기게 되므로, 해당 값이 곧 정답이 된다.
-
좀 더 자세한 설명과 직관적인 그림은 아래 링크를 참조하자.
https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence
✔ 구현된 코드
import sys
stringA = sys.stdin.readline().strip()
stringB = sys.stdin.readline().strip()
LCS = [[0]*(len(stringA)+1) for _ in range(len(stringB)+1)]
for i in range(len(stringB)):
for j in range(len(stringA)):
if stringB[i] == stringA[j]:
LCS[i+1][j+1] = LCS[i][j] + 1
else:
LCS[i+1][j+1] = max(LCS[i+1][j], LCS[i][j+1])
print(LCS[len(stringB)][len(stringA)])- 2차원 배열의 크기를 1씩 크게 잡았기 때문에 위의 점화식과는 조금 다를 수 있지만, 알고리즘을 이해했다면 쉽게 코드를 짤 수 있다.
✔ 관련 개념
- 다이나믹 프로그래밍 중 LCS 문제
