[Platinum V] LCS 4 - 13711
성능 요약
메모리: 139628 KB, 시간: 2684 ms
분류
가장 긴 증가하는 부분 수열: O(n log n)
문제 설명
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다.
1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.
출력
두 수열의 LCS의 크기를 출력한다.
풀이
아이디어
완전탐색으로 우선 만들었고 여기에 DP 적용
MAX = 100001
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[-1 * MAX] for _ in range(MAX)]
def LCS(indexA, indexB):
res = 1
if indexA == n or indexB == n:
return 0
if A[indexA] == B[indexB]:
return LCS(indexA+1, indexB+1) + 1
for nextA in range(indexA+1, n):
res = max(res, LCS(nextA, indexB))
for nextB in range(indexB+1, n):
res = max(res, LCS(indexA, nextB))
return res
print(LCS(0, 0))
적용한 모습은 아래와 같음
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[-1]*(n+1) for _ in range(n+1)]
def LCS(indexA, indexB):
if indexA == n or indexB == n:
return 0
if dp[indexA][indexB] != -1:
return dp[indexA][indexB]
if A[indexA] == B[indexB]:
dp[indexA][indexB] = LCS(indexA+1, indexB+1) + 1
else:
dp[indexA][indexB] = 1
for nextA in range(indexA+1, n):
dp[indexA][indexB] = max(dp[indexA][indexB], LCS(nextA, indexB))
for nextB in range(indexB+1, n):
dp[indexA][indexB] = max(dp[indexA][indexB], LCS(indexA, nextB))
return dp[indexA][indexB]
print(LCS(0, 0))
위와 같이 메모리초과가 발생함. 따라서 다른 방법을 찾아봐야함.
내 코드가 너무 아름다워서 미련을 못버리겠다..
아이디어 2
문제를 잘못읽었다. "1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B"라는 키워드를 놓쳐서 문제의 방향성을 잘못잡았다.
참고한 아이디어이며, 아이디어는 다음과 같다.
결국엔 리스트 A와 B에 들어있는 element들의 값은 모두 같다.
따라서 다음이 성립한다.
B.index(A[i]) 를 담은 리스트C의 lis는 두 리스트의 LCS와 같다.
이를 코드로 구현한것이 아래 코드이다.
import sys
import bisect
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [-1]*n
for idx, a in enumerate(A):
C[idx] = B.index(A[idx])
lis = [-float("INF")]
for c in C:
if c > lis[-1]:
lis.append(c)
else:
lis[bisect.bisect_left(lis, c)] = c
print(len(lis) - 1)하지만 이 코드는 Pypy에서는 통과하나 Python에서는 시간초과로 통과하지 못한다. 이를 해결하려면 C배열을 만드는 부분을 수정해야하는데, .index()로 인덱스 배열을 만드는것은 비효율적이다.
탐색을 할 때 파이썬에서 생각할 수 있는 자료구조는 set과 dictionary이다. 이를 이용해 인덱스 배열을 만드는 부분을 다시 생각해보았다.
아이디어 2 수정
두 자료구조 중 set은 순서가 없다는 특징 때문에 사용하기 어렵다. 따라서 딕셔너리 자료형을 사용하기로 결정했다.
모든 코드는 동일하게 사용하되, C배열을 만드는 부분을 수정한다.
import sys
import bisect
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
da = dict().fromkeys([i for i in range(n + 1)], -1)
db = dict().fromkeys([i for i in range(n + 1)], -1)
for i in range(n):
da[A[i]] = i
db[B[i]] = i
C = []
for i in range(n):
C.append(db[A[i]])
lis = [-float("INF")]
for c in C:
if c > lis[-1]:
lis.append(c)
else:
lis[bisect.bisect_left(lis, c)] = c
print(len(lis) - 1)
회고
우선 문제를 잘 읽어야 한다. Platinaum V 문제 답게 아이디어를 구상하는게 매우 어려웠다. 인터넷의 도움을 받았지만 나머지 구현에 대해서는 문제없이 진행하였다. 특히 아이디어1을 구현했을때 SRTBOT 과정을 그대로 따라갔고, 부분문제를 정확하게 구현하여 한번에 재귀함수를 구현했을때는 정말 쾌감이 좋았었다.(비록 틀리긴 했지만..) 조금 자신감이 생긴 듯 하다.
블로그에 올린 Platinaum 문제이다. 블로그에 올리지 못한 Platinaum 문제들의 경우 내가 풀었다고 하기 민망할 정도로 참고 비율이 높은 문제이다. 이 문제의 경우 많은 고민이 있었고, 그로 인한 성과가 있었다고 판단하였다.
