집합 - 최장 공통 부분순열(LCS)

박춘화·2022년 3월 2일
0

Algorithm

목록 보기
5/7

최장 공통 부분순열(LCS, Longest Common Subsequence)

최장 공통 부분순열은 두 순열의 각 부분순열 집합에서 공통으로 속하면서 길이가 가장 긴 부분순열을 찾는 알고리즘

최장 공통 부분문자열과의 차이점은 부분문자열과 다르게 부분순열 문제에서는 순서만 일치한다면 값의 연속성을 고려하지 않아도 된다.

최장 공통 부분순열을 해결하기 위해서는 각 순열의 부분순열 집합에서 공통된 최장 부분순열 행렬을 계산해야한다.

const createMatrix = (setA, setB) => {
  const matrix = Array(setB.length + 1)
      .fill(0)
      .map(() => Array(setA.length + 1).fill(0));

    const arrayA = Array.from(setA);
    const arrayB = Array.from(setB);

    for (let i = 1; i < setB.length + 1; i++) {
      for (let j = 1; j < setA.length + 1; j++) {
        if (arrayA[j - 1] === arrayB[i - 1]) {
          matrix[i][j] = matrix[i - 1][j - 1] + 1;
        } else {
          matrix[i][j] = Math.max(matrix[i][j - 1], matrix[i - 1][j]);
        }
      }
    }
  return matrix;
}

행렬의 값을 역추적하여 최장 공통 부분순열을 구할 수 있다. 역추적 과정은 DFS를 활용했다.

const LCS = (setA, setB) => {
  const arrayA = Array.from(setA);
  const arrayB = Array.from(setB);
  const matrix = createMatrix(setA, setB);
  const subMaxLength = matrix[setB.length][setA.length];
  const stack = [[setA.length, setB.length, ""]];

  let answer = null;

  while (stack.length > 0) {
    const [x, y, string] = stack.pop();

    if (string.length === subMaxLength) {
      answer = [string, subMaxLength];
      break;
    }

    if (x > 0 && y > 0) {
      if (arrayA[x - 1] === arrayB[y - 1]) {
        stack.push([x - 1, y - 1, arrayA[x - 1] + string]);
      } else {
        if (matrix[y][x] === matrix[y - 1][x]) {
          stack.push([x, y - 1, string]);
        }
        if (matrix[y][x] === matrix[y][x - 1]) {
          stack.push([x - 1, y, string]);
        }
      }
    }
  }

  return answer;
};
profile
함께 성장하는 개발자

0개의 댓글