[AlgorithmSolving][DP] JUNGOL_1220: 최장 공통 부분서열

1. 문제 내용

• 문제:

  2개의 문자열이 입력 될 경우 두 문자열의 최장공통부분 서열의 길이를 출력하는 프로그램을 작성하라.

  부분 서열이란, 원래 문자열에서 임의적으로 몇 개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열들을 말한다. 

    길이가 0인 문자열이나, 문자열 자기 자신도 부분 서열에 포함된다. 공통 부분 서열이란 문자열 집합 내에서 공통으로 존재하는 부분 서열을 뜻한다. 

  예를 들어, 다음과 같이 두개의 문자열이 주어진다고 하자.

  abcdgh  aedfhr

  위 두개의 수열의 최장공통부분서열은 adh 이고 길이는 3 이다.​ 

• 입력:

  입력은 두줄로 구성된다. 각 줄에는 최장공통부분서열의 길이를 구하고자 하는 문자열이 입력된다.  문자열의 길이가 1,000 개 이하인 문자열이 입력된다. 문자열은 알파벳 소문자와 숫자로 구성되어 있으며, 그 외의 문자는 입력되지 않는다.

• 출력:

  입력에 대한 최장공통부분서열의 길이를 출력한다.

2. 문제 유형 파악

이 문제는 두 문자열 사이의 “순서를 유지하면서” 공통으로 들어있는 가장 긴 문자열의 길이를 찾는 전형적인 최장 공통 부분 서열(LCS, Longest Common Subsequence) 문제입니다.

• 동적 계획법: 두 문자열을 한 글자씩 늘려가며 비교하고, 이전 단계에서 구해놓은 최장 길이를 다음 단계의 계산에 재사용해야 하므로 2차원 배열을 활용한 DP로 접근해야 합니다.
• 시간 복잡도 평가: 입력되는 문자열의 최대 길이가 1,000입니다. 두 문자열의 길이를 각각 N, M이라고 할 때, 2차원 배열을 모두 순회하는 $O(N /times M)$의 시간 복잡도를 가집니다. 최대 연산 횟수가 1,000 x 1,000 = 1,000,000(100만)번이므로, 시간 초과 없이 매우 안전하게 통과할 수 있습니다.

3. 문제를 풀기 위한 핵심 아이디어

이 문제를 해결하기 위한 핵심은 “두 문자열을 비교할 때 2차원 표를 만들고, 글자가 일치할 때와 일치하지 않을 때의 규칙(점화식)을 도출하는 것”입니다.

1. 상태의 정의와 배열 초기화

두 문자열을 각각 str1, str2라고 할 때, 2차원 DP 배열 $DP[i][j]$를 다음과 같이 정의합니다.

- DP[i][j] = `str1`의 i번째 글자까지와 `str2`의 j번째 글자까지 비교했을 때 도출된 LCS의 최장길이

문자열의 길이가 각각 N과 M이라면, 배열의 인덱스 참조 오류를 막고 기저 상태(Base Case)를 만들기 위해 가로세로 크기가 $(N+1) \times (M+1)$인 2차원 배열을 생성하고 모든 값을 0으로 초기화합니다. (0번째 인덱스는 ‘빈 문자열’과의 비교를 의미합니다.)

1. 점화식 도출(2가지 케이스)

배열을 이중 반복문으로 순회하면서, 현재 가리키고 있는 두 글자가 같은지 다른지에 따라 2가지 규칙을 적용합니다.

1. 두 글자가 같을 때(`str1[i-1] == str2[j-1]`)

  - 현재 비교하는 두 글자가 공통 부분 서열에 포함될 수 있습니다.
  - 이 경우, 두 글자가 추가되기 바로 직전 상태(즉, `str1`의 i-1번째, `str2`의 j-1번째까지의 최장길이)에서 1을 더해줍니다.
  - 점화식: DP[i][j] = DP[i-1][j-1] + 1 (표에서 왼쪽 대각선 위칸의 값 + 1)

2. 두 글자가 다를 때(`str1[i-1] != str2[j-1]`)

  - 현재 글자가 다르므로 새로운 길이를 추가할 수 없습니다.
  - 대신, 지금까지 누적된 최적의 결과를 그대로 물려받아야 합니다. `str1`의 이전 글자까지 비교한 최대 길이(DP[i-1][j])와 `str2`의 이전 글자까지 비교한 최대 길이(DP[i][j-1]) 중 더 큰 값을 그대로 가져옵니다.
  - 점화식: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) (표에서 위칸과 왼쪽 칸 중 더 큰 값)

1. 정답 출력

반복문이 모두 끝나고 나면, 두 문자열의 끝까지 모두 비교를 마친 지점인 배열의 맨 마지막 칸 즉, DP[N][M]에 전체 문자열의 최장 공통 부분 서열의 길이가 저장됩니다. 이 값을 그대로 출력하면 정답이 됩니다.

4. 코드

import sys

def solve():

    input = sys.stdin.readline

    input_string1 = input().rstrip()
    input_string2 = input().rstrip()

    n = len(input_string1)
    m = len(input_string2)

    dp = [[0] * (m+1) for _ in range(n+1)]

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

    print(dp[n][m])

if __name__ == "__main__":
    solve()

5. 복기 및 최적화

5.1 코드 복기

문자열 비교 알고리즘의 가장 기본이 되는 LCS(최장 공통 부분 서열) 문제를 정석적인 2차원 DP 바텀업(Bottom-Up) 방식으로 구현했습니다.

• 정확한 점화식 구현: 두 글자가 같을 때는 왼쪽 대각선 위(DP[i-1][j-1])의 값에 +1을 하고, 다를 때는 위(DP[i-1][j])와 왼쪽(DP[i][j-1]) 중 최댓값을 가져오는 규칙을 코드로 구현했습니다.
• 복잡도 평가: 두 문자열의 길이를 각각 N, M이라고 할 때, 이 코드의 시간 복잡도는 O(NxM), 공간 복잡도(메모리 사용량) 역시 2차원 배열의 크기인 $O(N \times M)$ 입니다. N과 M이 최대 1,000이므로 100만 번의 연산과 메모리 공간을 차지하며, 이는 제한 시간 내에 통과하기에 안전한 수치입니다.

5.2 최적화 포인트: 공간 복잡도 $O(N \times M) \rightarrow O(M)$으로 압축하기

시간 복잡도는 더 이상 줄일 수 없지만, 메모리 사용량은 극적으로 최적화할 수 있습니다.

현재 코드에서 2차원 DP 배열의 점화식을 살펴보면, i번째 행(현재 계산 중인 줄)을 채우기 위해 필요한 정보는 오직 i-1번째 행(바로 윗줄)의 데이터뿐입니다. i-2, i-3 행의 과거 데이터는 전혀 참조하고 있지 않습니다.

• 문제점: 1,000 x 1,000 크기의 2차원 배열을 통째로 메모리에 들고 있을 필요가 없습니다.
• 해결책 (토글링/슬라이딩 윈도우): 길이가 M+1인 1차원 배열 딱 2개(prev_dp, curr_dp)만 생성하여, 윗줄의 결과와 현재 줄의 결과를 번갈아 가며 갱신하면 메모리 사용량을 1/1000 수준으로 획기적으로 줄일 수 있습니다.

다음은 최적화를 적용한 코드입니다.

import sys

def solve():
    input = sys.stdin.readline

    input_string1 = input().rstrip()
    input_string2 = input().rstrip()

    n = len(input_string1)
    m = len(input_string2)

    # 전체 2차원 배열 대신, '이전 줄'을 저장할 1차원 배열 1개만 먼저 초기화
    prev_dp = [0] * (m + 1)

    for i in range(1, n + 1):
        # '현재 줄'을 계산하기 위한 새로운 1차원 배열 생성
        curr_dp = [0] * (m + 1)
        
        for j in range(1, m + 1):
            # 두 글자가 같을 때: 이전 줄(i-1)의 왼쪽 열(j-1) 값 + 1
            if input_string1[i-1] == input_string2[j-1]:
                curr_dp[j] = prev_dp[j-1] + 1
            # 두 글자가 다를 때: 이전 줄(i-1)의 현재 열(j)과 현재 줄(i)의 왼쪽 열(j-1) 비교
            else:
                curr_dp[j] = max(prev_dp[j], curr_dp[j-1])
        
        # 현재 줄의 계산이 끝났으므로, 다음 루프를 위해 현재 줄을 이전 줄로 교체(업데이트)
        prev_dp = curr_dp

    # 최종 결과는 마지막 갱신된 줄의 맨 끝에 저장됨
    print(prev_dp[m])

if __name__ == "__main__":
    solve()