백준 9252번 LCS
서론Permalink
LCS에서의 역추적 문제입니다. LCS(Longest Common Subsequence) 문제 자체를 풀어본 적이 없어서 풀이법을 떠올리기가 쉽지 않았습니다. 결국 다른 사람의 풀이법을 참고해서 풀었고 아래 링크에 너무 잘 정리되어있습니다.
*참고Permalink
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
제한 조건Permalink
- 시간제한 - 1초
시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 학습한 LCS 알고리즘이 O(MN)이고 문제에서 주어진 알파벳이 최대 1,000글자이니 M*N=1,000,000으로 충분히 풀 수 있습니다. 여기서 M, N은 알파벳의 길이입니다. 흔히 LCS로 부분 수열을 구하는 문제가 많이 나오니까 두 리스트의 M, N은 두 리스트의 길이가 됩니다.
- 메모리 제한 - 256MB
메모리 제한은 256MB입니다. 선언할 부분은 길이 1000짜리 문자열 두 개와 M*N = 1,000,000개 값을 가진 LCS[M][N] 리스트이고 python 기본 정수형 타입이 28byte이니 28MB이니 메모리는 충분합니다. 또 문제를 풀기 위해서 따로 자료구조를 가지는 게 아니니까 메모리는 걱정 없습니다.
문제를 풀다 보니까 애초에 메모리를 줄이라는 식의 문제가 아니면 문제에 필요한 값을 선언하는 데는 메모리 제한이 문제가 없고, 사용하는 자료구조에 메모리가 너무 많이 쌓일 때 문제가 되는 경우가 많았습니다. 앞으로는 딱히 메모리 제한에 대한 언급이 없거나 특별한 자료구조를 사용하는 경우가 아니면 메모리 제한은 신경 쓰지 않겠습니다.
LCS(Subsequence)Permalink
DP를 사용한 O(MN)의 방법을 사용합니다. 컨셉은 두 문자열을 한 개씩 탐색하며 문자열이 같다면 DP에서 한 칸 앞에 담긴 값에서 1의 더하는 것입니다. 한 칸 앞에 담긴 값에서도 두 문자열이 같았다면 또 한 칸 앞의 값에서 1을 더했기 때문에 연속된 문자열의 길이를 구할 수 있습니다. 문자열이 같지 않다면 앞에서 같았을 때의 길이를 가져옵니다.
문제에서는 문자열 자체도 역추적하라고 했기 때문에 추가적인 방법을 사용했습니다. LCS에 값이 담기는 과정을 보면 역추적하는 방법을 생각해 낼 수 있습니다. 참조링크에 자세하게 설명되어있습니다.
import sys
input = sys.stdin.readline
a = input().strip()
b = input().strip()
LCS = [[0]*(len(a)+1) for __ in range(len(b)+1)]
maxv = 0
for i in range(len(b)+1):
for j in range(len(a)+1):
if i == 0 or j == 0:
LCS[i][j] = 0
elif a[j-1] == b[i-1]:
LCS[i][j] = LCS[i-1][j-1]+1
maxv = LCS[i][j]
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
maxv = LCS[i][j]
print(maxv)
# pprint(LCS)
i = len(b)
j = len(a)
tmp = []
while LCS[i][j]:
if LCS[i][j-1] == LCS[i][j]:
j -= 1
elif LCS[i-1][j] == LCS[i][j]:
i -= 1
else:
tmp.append(a[j-1])
i -= 1
j -= 1
print(''.join(reversed(tmp)))
생각Permalink
역추적문제 자체를 BFS나 Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘에서 배워서 그런지 항상 지나쳐온 이전정점을 담는 리스트를 한 개 더 만든다고만 생각했는데, 이런 식으로도 풀 수 있다는 걸 알았습니다. 어떻게 보면 리스트를 한 개 선언하지 않으니 비용 측면에서도 이득인 것 같습니다. 역추적하는 문제가 나오면 고정관념에 갇히지 않고 어떻게든 풀기만 하면 된 것 같습니다. 하지만 역추적하는 과정이 메인 알고리즘보다 크면 안 되겠습니다.
DP 문제가 너무 어렵습니다... DP 관련 문제는 정석적인 풀이도 있겠지만 문제를 푸는 아이디어를 찾아야 해서 기계적으로 풀 수가 없는 것 같습니다. 시간이 되면 DP 관련 문제만 모아놓고 풀어서 DP 관련 아이디어를 떠올리는 것에 익숙해져야겠습니다.
*추가 LCS(Substring)Permalink
위의 문제는 Subsequence를 구하는 문제였기 때문에 중간에 두 문자열이 달라도 값을 유지했습니다. 하지만 Substring의 경우 문자열이 다르면 값이 초기화되기 때문에 아래와 같이 선언해주어야 합니다. 이렇게 하면 DP에 담긴 max 값이 문자열의 최장 길이입니다.
for i in range(len(b)+1):
for j in range(len(a)+1):
if i == 0 or j == 0:
LCS[i][j] = 0
elif a[j-1] == b[i-1]:
LCS[i][j] = LCS[i-1][j-1]+1
else:
LCS[i][j] = 0
BOJ내 다른 글 보기
댓글남기기