교대최소제곱법
[백준 파이썬 9252번 LCS2] DP에 문자열을 넣어서 드셔보세요 본문
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문자열 전체를 DP에 저장해서 사용하는 아이디어가 참신했다
공간 복잡도 O(n)로 짠 코드
def lcs(seq, tar):
dp = [''] * len(tar) # 배열의 크기는 두 번째로 도는 iter의 크기로 해야한다 ->5번라인으로
for i in range(len(seq)):
max_dp = ''
for j in range(len(tar)): # 배열의 크기만큼 돈다
if len(max_dp) < len(dp[j]):
max_dp = dp[j]
elif seq[i] == tar[j]:
dp[j] = max_dp + tar[j]
# 가장 큰 값 찾기
ans = ''
for s in dp:
if len(ans) < len(s):
ans = s
print(len(ans))
if len(ans):
print(ans)
A, B = input(), input()
lcs(A, B)
# DP
> ['C', 'CA', 'CAP', 'AC', 'ACA', 'ACAK']
이 경우 DP의 마지막에 최대 크기가 들어간다는 보장이 없기 때문에 탐색을 한 번 해주어야 하는 것 같다.
공간 복잡도 O(n**2)로 짠 코드
seq = [""] + list(input().rstrip())
tar = [""] + list(input().rstrip())
LCS = [[""] * len(tar) for _ in range(len(seq))]
for i in range(1, len(seq)):
for j in range(1, len(tar)):
if seq[i] == tar[j]:
LCS[i][j] = LCS[i-1][j-1] + seq[i]
else:
if len(LCS[i-1][j]) >= len(LCS[i][j-1]):
LCS[i][j] = LCS[i-1][j]
else:
LCS[i][j] = LCS[i][j-1]
result = LCS[-1][-1]
print(len(result), result, sep="\n")
# DP
> ['', 'C', 'CA', 'CAP', 'CAP', 'ACA', 'ACAK']
??? : 똑똑한 청년.
[백준 9252 파이썬] LCS 2 (골드 4, DP)
LCS 알고리즘에 역추적 섞기
velog.io
'코딩테스트' 카테고리의 다른 글
[백준 파이썬 2098번 외판원 순회] 비트마스킹이란 무엇인가? (0) | 2024.02.28 |
---|---|
[백준 파이썬 2110번 공유기 설치] 이진 탐색의 활용 (0) | 2023.11.21 |
[백준 파이썬 11049번 행렬 곱셈 순서] DP란 벽... (0) | 2023.10.26 |
[백준 파이썬 1948번 임계경로] 위상정렬 응용과 역추적의 활용 (1) | 2023.10.25 |
[백준 파이썬 1432번 그래프 수정] 생각의 전환의 전환 with 위상정렬 (0) | 2023.10.25 |