문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예제 입력 1
ACAYKP
CAPCAK
예제 출력 1
4
문제 해석
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다. 이 문제는 DP 접근 방식을 활용해 풀면 된다.
의사 코드
# 1. 사용자 입력 받기
# 2. 2차원 행렬로 만들기 (편의상 0번째는 0으로)
# 3. 같은 값이면 대각선 값에서 + 1 넣어주기
# 4. 같은 값이 없으면 왼쪽, 위쪽 값 중에 더 큰 값 가져오기. max # 5. 배열 마지막부터 역추적하고, 리버스하기 → 문자열의 길이를 찾는 것이기 때문에 백트래킹을 할 필요가 없다.
정답 코드
# 입력 받기
stringA = input()
stringB = input()
def lcs_length(stringA, stringB):
row = len(stringA) # 2차원 테이블을 만들거기 때문에 행으로 사용할 값 저장해주기
column = len(stringB) # 2차원 테이블을 만들거기 때문에 열로 사용할 값 저장해주기
# 2차원 테이블 만들기, 인덱스가 0부터 시작하기에 편의상 +1 해주기
lcs = [[ 0 for _ in range(column+1) ] for _ in range(row+1)] # 이 단계에서 이미 인덱스 0번 행과 열은 0으로 초기화 되었음
# 2차원 테이블에 반복문을 돌며 값 넣어주기
for i in range(1, row+1): # 인덱스 0번 부터 시작하기
for j in range(1, column+1): # 인덱스 0번 부터 시작하기
if stringA[i-1] == stringB[j-1]: # 문자열이 같다면
lcs[i][j] = lcs[i-1][j-1] + 1 # 이전 값에 +1 해주기, 그래야 최장으로 연속된 값을 찾을 수 있음
else: # 문자열이 다르다면
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]) # 왼쪽 값과 윗쪽 값중에 더 큰 값 저장하기. 그래야 순서를 유지하면서 연속된 값을 찾을 수 있음
# lcs 테이블의 마지막 값 반환하기 -> 이 값은 항상 전체 문자열을 고려한 최장 공통 부분 수열의 길이다.
return lcs[-1][-1]
# 결과 출력하기
print(lcs_length(stringA, stringB))
이 코드가 DP 알고리즘인 이유
① 문제를 작은 부분으로 나누어 해결한다.
lcs[i][j] 사용. lcs[i][j]는 stringA의 i번째 문자까지와 stringB의 j번째 문자까지의 LCS 길이를 나타낸다. 이는 전체 문제(두 문자열의 전체 LCS 찾기)를 더 작은 부분 문제들로 나눈 것이다.
② 중복 계산을 방지한다. (메모이제이션)
각 작은 문제의 결과를 lcs 배열에 저장하여 재사용한다. 한 번 계산된 lcs[i][j]의 값은 저장되어 나중에 다시 필요할 때 재계산 없이 사용된다.
③ 전체 문제의 최적해는 부분 문제들의 최적해다.
lcs[i][j]의 값은 이전에 계산된 더 작은 부분 문제들의 최적해를 이용하여 계산된다. 최종적으로 lcs[-1][-1]은 전체 문제의 최적해를 나타낸다.
'알고리즘' 카테고리의 다른 글
[백준] 2748번 피보나치 수 2 - Python (2) | 2024.09.30 |
---|---|
[백준] 11047번 동전 0 - Python (1) | 2024.09.30 |
[백준] 1991번 트리 순회 - Python (0) | 2024.09.22 |
[백준] 11654번 아스키 코드 - Python3 (0) | 2024.09.07 |
[백준] 15596번 정수 N개의 합 - Python3 (0) | 2024.09.07 |