[정글 WEEK04_알고리즘] LCS와 LIS

LCS(Longest Common Subsequence) - 최장 공통 부분 수열

"두 수열에서 순서를 유지하면서 공통으로 등장하는 가장 긴 부분 수열의 길이를 구하는 문제"

단순히 요소들이 모두 존재하는지 보기만 하면 안 되고 위치까지 고려한 비교가 필요함

 

🪄 활용 사례

버전 관리(diff), DNA 분석 

 

🪄 풀이 방법

DP → 시간 복잡도: O(N * M)  • N, M: 두 수열의 길이

 

💡 점화식

  1️⃣ 두 수열의 마지막 요소가 같다면, 그 문자를 포함한 LCS를 만들 수 있음

        해당 문자를 포함한 LCS를 만들기 위해 마지막 원소를 지우고, 짧아진 수열에 대한 LCS를 찾은 후 삭제한 원소를 붙여줌

        예) X = AB**C**, Y = DE**C** → C는 LCS에 포함됨
         → LCS(ABC, DEC) = LCS(AB, DE) + 1

  2️⃣ 두 수열의 마지막 요소가 다르다면, 둘 중 하나는 제외하고 비교함

        예) X = ABC, Y = DEK

          → LCS(ABC, DEK) = max(LCS(AB, DEK), LCS(ABC, DE))

LCS(i, j) = 
    0                              if i == 0 or j == 0
    LCS(i-1, j-1) + 1              if xi == yj
    max(LCS(i-1, j), LCS(i, j-1))  if xi ≠ yj

 

⌨️ 구현

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

 

🪄 예시

A = AGCAT
B = GAC

LCS: AC 또는 GC 또는 GA
➡ LCS 길이: 2

 

 

LIS(Longest Increasing Subsequence) - 최장 증가 부분 수열

주어진 수열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 것의 길이

정렬, 스케줄링, 최적 선택 등의 문제와 밀접

https://www.acmicpc.net/problem/11053

 

시간 복잡도: O(N^2) → O(N log N)

 

 

 

출처: https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4