알고리즘 스터디 - HackerRank : The Longest Common Subsequence

문제 해석

• subsequence는 sequence에서 몇몇 요소를 삭제하고 남은 것으로 볼 수 있다.
• 2개의 sequence의 LCS는 가장 긴 subsequence로 2개에게 흔한 요소이다.
• 만약 다양한 LCS가 있는데 길이가 같으면 하나만 출력한다.
• 여러 솔루션이 있으면 어느 것이라도 출력해 non-empty common subsequence가 존재함을 보장한다.

LCS(최장 공통 부분 순서)에 대하여

• LCS(Longest Common Subsequence)는 최장 공통 부분 순서를 말한다.
• 예를 들어, Business라는 단어가 있을 때 substring은 sine로 연속적으로 이어진 부분 문자열이 있고 subsequence는 연속적으로 이어지지 않았지만 순서는 맞는 snss가 될 수 있다.

입력

• A와 B의 사이즈 n, m을 입력 받음
• 그 다음 줄은 A의 리스트
• 마지막 줄은 B의 리스트

알고리즘 코드

• 해커랭크에 있는 MIT 강의를 들으면 바로 풀 수 있다. 물론, 1시간 넘게 걸려서 빠르게 이해하는데 초점을 두어야 한다.

def longestCommonSubsequence(a, b, n, m):
    c = [[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]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    
    lcs = []

    i, j = n, m
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            lcs.append(a[i-1])
            i -= 1
            j -= 1
        else:
            if c[i-1][j] > c[i][j-1]:
                i -= 1
            else:
                j -= 1
    return reversed(lcs)