def LCS(a,b,c):
global X,Y,Z
for i in range(1,X+1):
for j in range(1,Y+1):
for k in range(1,Z+1):
if a[i-1] == b[j-1] and b[j-1] == c[k-1]:
LCS_array[i][j][k] = LCS_array[i-1][j-1][k-1] +1
else:
LCS_array[i][j][k] = max(LCS_array[i][j][k], LCS_array[i-1][j][k], LCS_array[i][j-1][k], LCS_array[i][j][k-1])
a = input()
b = input()
c = input()
X = len(a)
Y = len(b)
Z = len(c)
LCS_array = [[[0 for _ in range(Z+1)] for _ in range(Y+1)] for _ in range(X+1)]
LCS(a,b,c)
print(LCS_array[X][Y][Z])
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
A = list(map(int,input().split()))
dict_A = {}
for k in range(N):
dict_A[A[k]] = k
B = list(map(int,input().split()))
convert_B = [0]*N
for ind,k in enumerate(B):
convert_B[ind] = dict_A[k]
LIS = [convert_B[0]]
for ind in range(1,N):
if convert_B[ind] > LIS[-1]:
LIS.append(convert_B[ind])
else:
left = -1
right = len(LIS)
while left + 1 < right:
mid = (left + right)//2
if LIS[mid] >= convert_B[ind]:
right = mid
else:
left = mid
LIS[right] = convert_B[ind]
print(len(LIS))
사실 이 문제는 LCS로 분류되어있지만, LIS 태그도 포함되어 있어야한다고 생각한다.
기존의 LCS로 하면 N^2이 걸리기 때문에, 입력사항을 보면 터질수 밖에 없다.
근데 우리는 여기서 문제의 조건을 잘 봐야한다.
문제의 조건에서 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때 라고 되어있다.
이 말은 각 수열에 있는 값들은 중복되는것은 없고, 하나하나가 유니크 하나는 것이다.
이 최장 부분수열에서는 인덱스가 증가하는 방향으로 부분수열을 구해야한다.
그렇다는 말은 A와 B라는 각 리스트가 있을 때, B의 각 값들이 A에 어디에 있는지 해놓으면,
def solution(A,B):
result = [[0]*(len(B)+1) for _ in range(len(A)+1)]
for i in range(1,len(A)+1):
for j in range(1,len(B)+1):
if A[i-1] == B[j-1]:
result[i][j] = result[i-1][j-1] + 1
return max(map(max,result))
A = input()
B = input()
print(solution(A,B))
LCS 문제이다. 근데 이전에 풀었던 LCS와 다른 문제였다.
기본적인 틀은 똑같다. 대신 이 문제는 연속된 문자열이어야 하기 때문에, A[i-1] != B[i-1]일때는 아무것도 해주지 않는다.
# 9251 LCS
def LCS(SA,SB,SALEN,SBLEN):
global LCS_list
for i in range(1,SALEN+1):
for j in range(1,SBLEN+1):
if SA[i-1] == SB[j-1]:
LCS_list[i][j] = LCS_list[i-1][j-1]+1
else:
LCS_list[i][j] = max(LCS_list[i-1][j],LCS_list[i][j-1])
A = list(input())
B = list(input())
lenA = len(A)
lenB = len(B)
LCS_list = [[0]*(lenB+1) for _ in range(lenA+1)]
LCS(A,B,lenA,lenB)
print(LCS_list[lenA][lenB])
# Longest Common Subsequence
# 최장 공통 부분 수열
def LCSlength(X,Y):
for i in range(1,len(X)+1):
for j in range(1,len(Y)+1):
if X[i-1] == Y[j-1]:
LCS_ARRAY[i][j] = LCS_ARRAY[i-1][j-1] + 1
else:
LCS_ARRAY[i][j] = max(LCS_ARRAY[i][j-1],LCS_ARRAY[i-1][j])
def findBackTrack(C,X,Y,i,j):
if i == 0 or j == 0:
return ''
if X[i-1] == Y[j-1]:
return findBackTrack(C,X,Y,i-1,j-1) + X[i-1]
if C[i][j-1] > C[i-1][j]:
return findBackTrack(C,X,Y,i,j-1)
return findBackTrack(C,X,Y,i-1,j)
string_1 = list(input())
string_2 = list(input())
LCS_ARRAY = [[0]*(len(string_2)+1) for _ in range(len(string_1)+1)]
LCSlength(string_1,string_2)
result = findBackTrack(LCS_ARRAY,string_1,string_2,len(string_1),len(string_2))
print(len(result))
print(result)
LIS와 LCS같은 DP 문제들은 반복 숙달이 되지 않으면 실전에서 푸는게 어려워 보인다.
제가 이해한 기본적인 원리는 다음과 같다. 문자열 S1 과 문자열 S2가 있으면, 이 두 문자열의 길이만큼의 2차원 행렬을 만들어준다.
이 행렬은 두 문자열이 같은 문자열을 얼마나 가지고 있는지 판별이 되는 행렬이다. 이행렬의 이름을 LCS라 하고, 이 행렬의 크기는 (문자열 S1의 길이 +1) X (문자열 S2의 길이 +1)이 된다. 왜냐하면 아무것도 선택하지 않았을때를 초기화 해주는 부분이 있기 때문이다.
그리고 S1,S2를 기준으로 2중 for문을 돌려준다. 그러면서 s1과 s2에서 똑같은 문자열이 발견이 되면,
LCS[i][j]에 = LCS[i-1][j-1] +1 을 해준다.
왜 대각선 성분에 있는걸 더해주는 이유는 똑같은 문자열이 발견되기 직전의 각각의 index에 존재하는 값이 해당 부분직전까지의 최대값이기 때문이다.
코드를 보면 좀 헷갈리는 이유는 S1,S2의 index는 0부터 시작하기 때문이다. s1,s2의 i,j index의 LCS의 길이값은 LCS의 i+1,j+1 index에 저장이 된다.
만약 같지 않을 경우, [i-1, j], [i,j-1] 둘중 큰 값을 넣어주면 된다.
이렇게 구한 LCS를 이용해서 역추적으로 최장 공통 부분수열을 구성 값을 구해준다.
이 방법은 단 1개를 구하는 것이므로, 다른 방법은 위의 위키를 참조하거나, 다른 사람 블로그를 참조하길 바란다.
백트래킹으로 찾는 방법인데, 각가의 끝 인덱스에서 시작해서 만약에 두 인덱스에서의 S1,S2의 값이 같으면, 그 부분을 결과에 return 시켜주고, 현재 index는 두 값이 같기 때문에, i-1,j-1위치에서 백트래킹을 해준다.
그리고 그 외에는 LCS의 길이가 변경되는 순간이 같은 문자열이 존재하는 구간이기 때문에,
[i-1][j] 와 [j][j-1의 LCS의 길이를 비교해서 더 큰 곳으로 이동해서 계쏙 반복을 해준다.