알고리즘 – LCS (Python)

• LCS (Longest Common Subsequence) 란?
  • 최장 공통 부분수열이라고도 부르며 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 방법
  • 시간 복잡도
    • O(a₁ × a₂ × a₃ … × a_n)

---

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

백준 9252번 – LCS 2를 예시로 설명하겠습니다.

문제)
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제

답)
해당 부분 수열의 값, 길이

• 풀이 방법
  • 먼저 두 수열을 비교를 통해 최대 길이를 구합니다
    • a 수열의 i번째와 b 수열의 j번째가 같은 경우
      • LCS[i][j] = LCS[i-1][j-1]+1
    • a 수열의 i번째와 b 수열의 j번째가 같은 경우
      • LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

자 이제 거의 다 왔습니다! 😃😃

길이를 구한 수열의 값만 찾으면 되는데요! 순서는 아래와 같습니다.

• 수열 찾기 순서

1. 리스트의 마지막 값 ( LCS[-1][-1])을 기준 값으로 정한다
2. 인접 값에 동일한 값이 있을경우 해당 위치로 이동 ( LCS[move_y-1][move_x], LCS[move_y][move_x-1] )
3. 인접 값에 동일한 값이 없을경우 대각선으로 이동 후 해당 값 저장 ( LCS[move_y-1][move_x-1] )
4. 최장 길이 도달 시 연산 종료

• 결과 코드

# Python Code

import sys
N = list(sys.stdin.readline().strip())
M = list(sys.stdin.readline().strip())
intersection = set(N) & set(M) # 두 수열의 교집합

if len(intersection) == 0: # 두 수열간 같은 값이 존재하지않을경우
    print(0)
else:
    y_len = len(N)+1
    x_len = len(M)+1
    LCS = [ [0 for _ in range(x_len)] for _ in range(y_len) ]

    for i in range(1, y_len):
        for j in range(1, x_len):
            
            if N[i-1] == M[j-1]: # 수열의 값이 일치할 경우
                LCS[i][j] = LCS[i-1][j-1]+1
            else:
                LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])

    # 초기 기준값
    move_x = x_len-1
    move_y = y_len-1
    standard = LCS[move_y][move_x]
    result_str = []

    while True:
        if LCS[move_y][move_x-1] == standard: # 인접 길이 값 중 동일한 값이 있을경우 해당 위치로 이동
            move_x -= 1
        elif LCS[move_y-1][move_x] == standard:
            move_y -= 1
        else:
            # 인접 길이 값 중 중 동일한 값이 없을경우 대각선 이동
            move_x -= 1
            move_y -= 1
            standard = LCS[move_y][move_x]
            result_str.append(N[move_y])
        
        # 최장 길이 값에 도달할 경우
        if len(result_str) >= LCS[-1][-1]: break

    print(LCS[-1][-1])
    for _ in reversed(result_str): sys.stdout.write(_)

문제 풀이 끝! 😀

참고자료

• Longest_common_substring_problem
• 최장 공통 부분 수열
• 백준 – LCS 2
• 백준 – LCS 3