[바미] Dynamic programming - LCS 알고리즘 구현하기.

Longest Common Subsequence?

Longest Common Subsequence (LCS) 알고리즘은 주어진 두 개의 문자열에서 가장 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이란, 원래 문자열의 일부 문자들을 순서대로 골라 만든 새로운 문자열을 말하는데 

예를 들어, "ABCDGH"와 "AEDFHR" 두 문자열이 있다고 가정해보죠. 이 두 문자열에서 가장 긴 공통 부분 문자열은 "ADH"가 되죠?

이 때, "ADH"는 "ABCGD"와 "AEDFHR"의 부분 문자열이지만, "ACF"는 "ABCGD"와 "AEDFHR"의 부분 문자열이 아니게 돼요.

 

LCS 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)을 활용하여 구현됩니다. 구체적으로, 두 문자열 str1과 str2에 대해 dp 배열을 다음과 같이 정의합니다.

• dp[i][j]: str1의 0번 인덱스부터 i-1번 인덱스까지의 부분 문자열과 str2의 0번 인덱스부터 j-1번 인덱스까지의 부분 문자열의 LCS 길이

dp 배열의 값은 다음과 같이 계산됩니다.

• dp[0][j] = 0 (0 ≤ j ≤ |str2|)
• dp[i][0] = 0 (0 ≤ i ≤ |str1|)
• dp[i][j] = dp[i-1][j-1] + 1 (if str1[i-1] = str2[j-1])
• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (otherwise)

위의 점화식에서 |는 문자열의 길이를 의미합니다. 마지막 두 줄의 점화식은 각각, 현재 비교하는 두 문자가 다르다면 두 문자열 중 하나를 하나씩 줄여가면서 계산하고, 현재 비교하는 두 문자가 같다면 두 문자열 모두를 하나씩 줄여가면서 계산하는 것을 나타냅니다. 최종적으로 dp[|str1|][|str2|] 값이 두 문자열의 LCS 길이가 됩니다.

 

그럼 이제 코드로 구현해 볼까요?

---

코드 구현

function longestCommonSubsequence(str1, str2) {
  const m = str1.length;
  const n = str2.length;
  const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0)); // DP 테이블 생성
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // 두 문자가 같으면 대각선 위 값 + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 다르면 위 또는 왼쪽 값 중 큰 값으로 갱신
      }
    }
  }

  const lcs = []; // LCS를 저장할 배열 생성
  let i = m, j = n;

  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      lcs.unshift(str1[i - 1]); // 두 문자가 같으면 LCS 배열에 추가하고 대각선 위로 이동
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--; // 왼쪽 값이 더 크면 위로 이동
    } else {
      j--; // 위 값이 더 크면 왼쪽으로 이동
    }
  }

  return lcs.join(''); // LCS 배열을 문자열로 변환하여 반환
}

---

코드 설명

Longest Common Subsequence 알고리즘은 Dynamic Programming(DP)을 활용한 방식으로, 입력된 두 문자열 str1과 str2의 최장 공통 부분 문자열(Longest Common Subsequence, LCS)을 찾습니다.

 

DP 테이블 dp을 생성하여 dp[i][j]는 str1의 i번째 문자와 str2의 j번째 문자까지 고려했을 때의 LCS의 길이를 저장합니다. dp[0][0]은 빈 문자열을 고려한 값이며, dp[1][1]부터 각 문자열의 문자를 하나씩 추가하면서 테이블을 채워나갑니다.

 

만약 두 문자열의 i번째 문자와 j번째 문자가 같다면, DP 테이블에서 대각선 위에 있는 dp[i-1][j-1] 값에 1을 더한 값을 저장합니다. 다르다면 DP 테이블에서 위쪽 dp[i-1][j]과 왼쪽 dp[i][j-1] 값 중 큰 값을 저장합니다.

 

DP 테이블을 완성한 후, 역추적을 통해 LCS 배열을 구합니다. lcs 배열을 생성한 DP 테이블에서 구한 LCS 길이를 바탕으로 LCS를 구하기 위해서는 역추적(reverse tracing)을 수행해야 합니다. 이를 위해 LCS 배열 lcs를 빈 배열로 초기화하고, i와 j 변수를 str1과 str2의 길이로 초기화합니다.

 

그리고 i가 0보다 크고 j가 0보다 큰 동안 다음을 반복합니다.

• 만약 str1[i-1]과 str2[j-1]이 같다면, lcs 배열의 맨 앞에 str1[i-1]를 추가하고, i와 j를 각각 1씩 감소시킵니다.
• 만약 dp[i-1][j]가 dp[i][j-1]보다 크다면, i를 1 감소시킵니다.
• 그렇지 않으면, j를 1 감소시킵니다.

위의 과정을 마치면 lcs 배열에는 LCS의 문자들이 역순으로 저장되는데 join() 메서드를 사용하여 배열을 문자열로 변환하여 반환합니다.

 

추가적으로 Longest Common Subsequence 알고리즘은 O(mn)의 시간복잡도를 가지며, m과 n은 각각 str1과 str2의 길이입니다.

이 알고리즘의 주요 아이디어는 DP의 Bottom-Up 방식으로, 작은 부분 문제의 해답을 이용하여 더 큰 부분 문제의 해답을 계산하게 되죠.