[코테] Lis & Lcs

LIS (Longest Increasing Subsequence)

1. 어떤 수열에서 순서를 유지하며 부분 수열로서 증가하는 원소들의 최대 길이를 찾는 문제

2. [10, 22, 9, 33, 21, 50, 41, 60, 80]일 때, LIS는 [10, 22, 33, 50, 60, 80]

3. 각 위치에서 현재 원소까지의 LIS를 구할 때, 이전 위치의 원소들과 비교하면서 더 큰 값의 LIS를 업데이트

n = int(input())
arr = list(map(int, input().split()))

dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i): # 현재 기준 i-1까지 확인
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

LCS (Longest Common Subsequence)

1. 두 개의 수열에서 공통으로 나타나는 부분 수열 중 가장 긴 것을 찾는 문제

2. 두 수열 "ABCD" & "ACDF"일 때, 공통 부분 수열은 "ACD"

3. 두 수열의 각 문자를 비교하면서 LCS의 길이를 저장하는 2차원 배열을 구성

4. 현재 문자가 같으면 왼쪽 대각선 위의 값에서 1을 더한 값을, 다르면 바로 위나 왼쪽의 값 중 큰 값을 선택하여 현재 위치에 저장

5. 배열의 오른쪽 아래 값이 최종적인 LCS의 길이

M = list(str(input()))
N = list(str(input()))

dp = [[0 for _ in range(len(N)+1)] for _ in range(len(M)+1)]

for i in range(1, len(M)+1):
    for j in range(1, len(N)+1):
        if M[i-1] == N[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[len(M)][len(N)])