집합 - 최장 증가 부분순열(LIS)

박춘화·2022년 3월 2일
0

Algorithm

목록 보기
6/7

최장 증가 부분순열(Longest Increasing Subsequence)

최장 증가 부분순열은 순열의 부분순열 집합에서 오름차순으로 정렬된 부분순열 중에 길이가 가장 긴 부분순열을 구하는 알고리즘

먼저 최장 증가 부분순열의 길이를 계산하기 위해 길이 배열을 계산한다. 그 후에 길이 배열을 활용하여 역추적을 하면 최장 증가 부분순열을 구할 수 있다. 역추적 과정은 DFS를 활용했다.

const LIS = (set) => {
  const getIndexArray = (array, maxLength) => {
    return array
      .map((length, index) => {
        return { length, index };
      })
      .filter(({ length, index }) => length === maxLength)
      .map(({ length, index }) => index);
  };

  const length = set.length;
  const lengthArray = Array(length).fill(1);

  for (let i = 1; i < length; i++) {
    for (let j = 0; j < i; j++) {
      if (set[i] >= set[j]) {
        lengthArray[i] = Math.max(lengthArray[i], lengthArray[j] + 1);
      }
    }
  }

  const maxLength = Math.max(...lengthArray);
  const maxIndexes = getIndexArray(lengthArray, maxLength);
  const answer = [];

  while (maxIndexes.length > 0) {
    const maxIndex = maxIndexes.pop();
    const stack = [[maxLength, maxIndex, [set[maxIndex]]]];

    while (stack.length > 0) {
      const [length, currentIndex, sequence] = stack.pop();

      if (length === 1) {
        answer.push(sequence);
        continue;
      }

      const indexArray = getIndexArray(lengthArray, length - 1);
      indexArray.forEach((index) => {
        if (index < currentIndex && set[index] < sequence[0]) {
          const copiedSequence = sequence.slice();
          copiedSequence.unshift(set[index]);
          stack.push([length - 1, index, copiedSequence]);
        }
      });
    }
  }

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

0개의 댓글