[Algorithm] LCS(Longest Common Subsequence) 최장 공통 부분 수열

📖소개

이는 2개의 문자열이 주어졌을 때, 해당 두 문자열에 공통적으로 포함되는 부분 수열 중에 가장 긴 것을 의미한다.

✍️Example

ACAYKP와 CAPCAK가 있다고 가정하자.
이 때, 두개의 문자열내에 존재하는 가장 긴 공통 부분 LCS는 ACAK이다.

이를 구하는 방법은 대표적으로 2개가 존재한다.

• Brute Force ( 시간복잡도 : O(2ⁿ) )

  • Brute Force의 접근 방식
    0. 문자열 str1, 문자열 str2가 존재한다 가정
    1. 문자열 str1의 모든 부분 수열을 array1 내에 저장
    2. 문자열 str2의 모든 부분 수열을 array2 내에 저장
    3. array1과 array2내에 공통된 것 중 가장 긴 것을 출력

    매우 비효율적임.

• Dynamic Programming ( 시간복잡도 : O(n*m) )

  • Dynamic Programming의 접근 방식
    0. 점화식 도출
       • arr1[i]와 arr2[j]가 같은 경우
         dp[i][j] = dp[i-1][j-1] + 1;
       • arr1[i]와 arr2[j]가 다른 경우
         dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    1. 점화식을 기반해서 문제해결

🔥DP로 문제 해결

위처럼 설명하면, 솔직히 잘 이해가 안될 수도 있다 생각해서 아래에 DP를 통한 방식의 시각적인 정보를 추가했다.

LCS 길이 구하기

• 초기설정
  dp[arr1.length+1][arr2.length+1] 만큼의 크기로 만든다.

  dp[i][j] 일때,
  i == 0 or j == 0 이면 dp[i][j] = 0으로 초기화

• arr1[i]와 arr2[j]가 다른 경우

  i==1 and j==2일 때를 한번 보자
  'A'와 'B'는 서로 다른 문자이다.
  그렇기에 이전의 상태를 그대로 가지고 와야한다.

• arr1[i]와 arr2[j]가 같은 경우

  i==2 and j==1일 때를 한번 보자
  'C'와 'C'는 서로 같은 문자이다.

  그렇기 때문에 현재 위치에서의 LCS 길이는 이전 상태 중 어떤 부분수열로서 채택되지 않은 것을 선택해야 합니다.

  즉 dp[i-1][j-1] 에 +1 을 해서 상태를 갱신해주게 된다.

  이러한 형태로 진행된 이후 dp[arr1.length][arr2.length]번째가 LCS 길이가 된다.

LCS 문자를 구하려면?

문자를 트래킹해야한다.

• 방향을 구분할 수 있는 요소를 저장해 둔다.
• i==arr1.length and j == arr2.length 부터 방향을 따라 돌아간다.
  • 방향이 대각선이라면, 동일 문자이기 때문에, 해당 문자를 Stack에 넣는다.
• Stack을 pop하면서 top에 있는 요소를 출력한다.

위와 같이 동작을 구현하면, 별로 힘들이지않고 LCS 자체를 출력할 수 있을 것이다.