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

LIS알고리즘?

Longest Increasing Subsequence (LIS) 알고리즘은 어떤 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘을 말하는데요.

예를 들어, 수열 [3, 1, 5, 2, 4, 9]에서 LIS는 [1, 2, 4, 9]이 되죠.

LIS 알고리즘은 동적 프로그래밍 기법을 사용하여 해결할 수 있는데 문제를 해결하기 위해 각 요소에 대한 최장 증가 수열의 길이를

계산하고, 최종적으로 이들 중 최대 값을 찾아주죠.

먼저 Bottom-up 방식으로 LIS 알고리즘을 구현해 보겠습니다. 이 방식에서는 DP table을 채우기 위해 이전 값들을 사용하는 방식으로 구현됩니다.

Bottom-up 방식

코드 구현

function longestIncreasingSubsequence(nums) {
  // 1. 초기화
  const dp = Array(nums.length).fill(1);

  // 2. DP table 채우기
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  // 3. 최댓값 찾기
  let maxLength = 0;
  for (let i = 0; i < nums.length; i++) {
    maxLength = Math.max(maxLength, dp[i]);
  }

  return maxLength;
}

코드 설명

위 코드에서는 다음과 같은 과정을 거쳐요.

1. 초기화 - DP table을 저장하기 위한 배열을 만들고, 각 요소에 대한 최장 증가 수열의 길이를 1로 초기화해요.
2. DP table 채우기 - DP table을 채우기 위해 이중 for loop을 사용하는데 외부 루프는 현재 값을 가리키고, 내부 루프는 현재 값 이전의 값들을 가리키는데 이전 값이 현재 값보다 작으면, 현재 값의 최장 증가 수열의 길이는 이전 값의 최장 증가 수열의 길이에서 1을 더한 것과 같아요. 이를 DP table에 저장하죠.
3. 최댓값 찾기- DP table에서 최대 값을 찾아 반환해줘요.

위 코드를 통해 주어진 수열의 LIS의 길이를 찾을 수 있어요.

이 알고리즘의 시간 복잡도는 O(n^2)이며, 이보다 빠르게 구현할 수 있는 O(nlogn) 알고리즘도 있어요.

---

O(nlogn) 알고리즘을 사용한 방식

O(nlogn) 알고리즘은 이진 탐색(Binary Search)을 이용하여 LIS를 찾아내는 알고리즘인데 이진 탐색은 정렬된 배열에서 특정 값을

찾는 알고리즘으로, 배열을 이용하여 특정 값을 찾을 때 일반적으로 사용되고 있어요.

코드 구현

function LIS(arr) {
  // arr[i]는 길이가 i인 LIS를 만들기 위해 필요한 가장 작은 마지막 요소
  const dp = [arr[0]];
  const len = arr.length;

  for (let i = 1; i < len; i++) {
    const cur = arr[i];
    // 현재 값보다 큰 값이 나타나면 그 위치에 현재 값을 삽입합니다.
    if (cur > dp[dp.length - 1]) {
      dp.push(cur);
    } else {
      // 이진 탐색을 이용하여 LIS의 길이를 구합니다.
      let start = 0;
      let end = dp.length - 1;
      let mid = 0;

      while (start < end) {
        mid = Math.floor((start + end) / 2);
        if (dp[mid] >= cur) {
          end = mid;
        } else {
          start = mid + 1;
        }
      }
      dp[end] = cur;
    }
  }
  // LIS의 길이를 반환합니다.
  return dp.length;
}

// 예시
const arr = [3, 2, 6, 4, 5, 1];
console.log(LIS(arr)); // 3

코드 설명

먼저 O(nlogn) 알고리즘은 이진 탐색을 사용하기 때문에 이진 탐색을 위해 배열을 만들고, 이 배열은 LIS의 길이가 i인 부분 수열을 만들기 위해 필요한 가장 작은 마지막 요소를 저장해줘요.

 

그러니까 arr[i]는 길이가 i인 LIS를 만들기 위해 필요한 가장 작은 마지막 요소를 의미하게 되는 것이죠.

예를 들어, [0, 0, 0, 0, 0] 배열이 있다면, arr[1]은 길이가 1인 LIS를 만들기 위해 필요한 가장 작은 마지막 요소, arr[2]는 길이가 2인 LIS를 만들기 위해 필요한 가장 작은 마지막 요소를 의미하는 셈이 되는 것이죠.

그 다음에 이진 탐색을 이용하여 LIS의 길이를 구하게 되는데요. 이진 탐색을 수행할 때, 현재 값보다 큰 값이 나타나면 그 위치에 현재

값을 삽입하고, 그렇지 않으면, 현재 값으로 해당 위치의 값을 대체하는데 이 과정에서 arr 배열도 업데이트 되는 것이죠.

 

이진 탐색을 이용하여 LIS를 구하는 O(nlogn) 알고리즘은, 전체 시간 복잡도가 O(nlogn)으로 효율적이죠.

---

두 코드 모두 LIS를 구하는 방법은 다르지만, 모두 시간 복잡도가 O(n^2) 보다 빠르게 구현되고 있어요.

 

언제 사용하면 좋을까?

1. 최장 증가 부분 수열 문제를 해결해야 하는 경우

주어진 수열을 오름차순으로 정렬하기 위해 필요한 최소한의 연산을 찾거나, 숫자가 증가하는 순서대로 작업이 수행되는 경우 등에서 사용할 수 있습니다.

2. 두 가지 연속적인 배열에서 최장 공통 증가 부분 수열을 찾아야 하는 경우

두 문서를 비교하여 공통적으로 가지고 있는 단어들의 최장 증가 부분 수열을 찾아 문서 유사도를 측정하는 경우 등에서 사용할 수 있습니다.

3. 다른 문제를 해결하기 위한 보조 알고리즘이 필요한 경우

알고리즘 최적화 문제 등에서 이 알고리즘을 활용하여 효율적인 문제 해결 방법을 찾을 수 있습니다.

요약하자면 수열의 순서를 파악해야 하는 문제를 해결해야 할 때나 최장 증가 부분 수열을 찾아야 하는 경우에는 Longest Increasing Subsequence 알고리즘을 사용할 수 있습니다.