Post

LIS 알고리즘

LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘에 대해 정리한 페이지입니다.

Posted
Preview Image
By HyunJinNo
13 min read
LIS 알고리즘

Tags
Algorithm

개요

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘에 대해 정리한 페이지입니다.

LIS (Longest Increasing Subsequence, 최장 증가 부분 수열)

개념

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘입니다. 예를 들어, [10, 20, 10, 30, 20, 50]이라는 수열에서 LIS는 [10, 20, 30, 50]이며 LIS의 길이는 4입니다.

1
2
3
4
5
6

수열: [10, 20, 10, 30, 20, 50]

-----------------------------

LIS: [10, 20, 30, 50]
길이: 4

구현

최장 증가 부분 수열을 찾는 알고리즘은 다음 두 가지 방법이 존재합니다.

DP 방법: O(N²)

다음과 같이 DP 방법으로 LIS를 구할 수 있습니다. arr[i]를 마지막으로 하는 LIS의 길이를 구해서 전체에서 최댓값을 찾는 방식으로 LIS의 길이를 구할 수 있습니다. DP 방법의 시간 복잡도는 O(N²)입니다.

i012345
arr356257
dp123124
1
2
3
4
5
6
7
8
9
10
11
12
13
14

const arr = [3, 5, 6, 2, 5, 7];
const N = arr.length; // 6
const dp = Array(N).fill(1); // dp[i]: arr[i]를 마지막으로 하는 LIS의 길이

for (let i = 1; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

console.log(dp); // [1, 2, 3, 1, 2, 4]
console.log(Math.max(...dp)); // 최장 증가 부분 수열의 길이: 4

만약 길이뿐만 아니라 실제 LIS까지 필요한 경우 추가로 다음과 같이 구현할 수 있습니다. 원본 수열의 가장 마지막 인덱스부터 시작해서 0번 인덱스까지 역순으로 탐색하여 LIS를 얻을 수 있습니다.

i012345
arr356257
dp123124
       
LIS356  7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* ... */
/* 위의 코드와 동일 */

let result = [];
let count = Math.max(...dp); // 4
let index = N - 1; // 5

while (count > 0) {
  if (dp[index] === count) {
    result.push(arr[index]);
    count--;
  }

  index--;
}

console.log(result.reverse()); // [3, 5, 6, 7]

이분 탐색 방법: O(N log N)

아래와 같이 이분 탐색 방법으로 LIS를 구할 수 있습니다. 위의 DP 방법의 시간 복잡도는 O(N²)이지만, 이분 탐색 방법의 시간 복잡도는 O(N log N)이므로, LIS를 구할 때는 이분 탐색 방법을 사용하는 것이 좋습니다.

이분 탐색 방법의 아이디어는 길이가 같은 증가 부분 수열들 중에서 마지막 숫자가 최소인 것을 남기는 것입니다. 길이가 동일한 여러 LIS가 존재하는 경우 마지막 숫자가 작을 수록 다음 숫자가 들어오는 경우 앞으로 더 긴 수열을 만들 가능성이 높다는 것이 핵심입니다. 이를 위해 원본 배열의 첫번째 숫자부터 확인하면서 새로운 숫자(=x)를 확인할 때마다 길이가 L인 부분 수열 중 마지막 숫자가 x 이상인 첫 번째 것을 찾아서 x로 교체하는 방식으로 구현합니다. 이를 이분 탐색으로 빠르게 찾는 것이 핵심입니다.

예를 들어 [3, 5, 6, 2, 5, 7]이라는 배열이 있는 경우 각 숫자를 확인할 때마다 다음과 같은 과정을 통해 LIS를 구하게 됩니다. 여기서 lis[i]는 길이가 i + 1 인 LIS 중 마지막 숫자가 최소인 것을 의미합니다.

  1. 숫자 3

    첫 숫자 3까지의 LIS의 길이는 당연히 1이며, 길이가 1인 LIS의 마지막 숫자는 3입니다.

    i012345
    arr3     
    lis3     

  2. 숫자 5

    숫자 5가 들어오는 경우 이전까지의 LIS의 끝부분에 숫자 5를 추가할 수 있으므로 숫자 5까지의 LIS의 길이는 2이며, 길이가 2인 LIS의 마지막 숫자는 5입니다.

    i012345
    arr35    
    lis35    

  3. 숫자 6

    숫자 6가 들어오는 경우 이전까지의 LIS의 끝부분에 숫자 6를 추가할 수 있으므로 숫자 6까지의 LIS의 길이는 3이며, 길이가 3인 LIS의 마지막 숫자는 6입니다.

    i012345
    arr356   
    lis356   

  4. 숫자 2

    숫자 2가 들어오는 경우 숫자 6 뒤에 숫자 2를 추가할 수 없습니다. 또한 숫자 2는 현재 길이가 1인 LIS의 마지막 숫자 3보다 작으므로 길이가 1인 LIS의 마지막 숫자를 1로 업데이트합니다.

    i012345
    arr3562  
    lis256   

  5. 숫자 5

    숫자 5가 들어오는 경우 lis[0] 값보다 크고, lis[2] 값보다 작으므로 이분 탐색을 통해 lis 배열 내 업데이트할 인덱스를 찾습니다. 이 경우 lis[i]를 업데이트하게 됩니다.

    i012345
    arr35625 
    lis256   

  6. 숫자 7

    숫자 7이 들어오는 경우 lis[2] 값보다 크므로 숫자 6 뒤에 7을 추가할 수 있습니다. 따라서 마지막 인덱스까지 숫자를 확인한 경우 LIS의 길이는 4(=lis.length)입니다.

    i012345
    arr356257
    lis2567  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const arr = [3, 5, 6, 2, 5, 7];
const N = arr.length; // 6
const lis = [arr[0]]; // 길이가 index + 1 인 증가 부분 수열들 중에서 가장 마지막 숫자가 최소인 것

for (let i = 1; i < N; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
  }
}

console.log(lis); // [2, 5, 6, 7]
console.log(lis.length); // 최장 증가 부분 수열의 길이: 4

만약 길이뿐만 아니라 실제 LIS까지 필요한 경우 DP 방법의 원리와 동일하게, 숫자를 확인할 때 arr[i]를 마지막으로 하는 LIS의 길이를 저장할 배열을 추가해야 합니다. 아래와 같이 length 배열을 추가한 후, 원본 수열의 가장 마지막 인덱스부터 시작해서 0번 인덱스까지 역순으로 탐색하여 LIS를 얻을 수 있습니다.

i012345
arr356257
lis2567  
length123124
       
LIS356  7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

const arr = [3, 5, 6, 2, 5, 7];
const N = arr.length; // 6
const lis = [arr[0]]; // 길이가 index + 1 인 증가 부분 수열들 중에서 가장 마지막 숫자가 최소인 것
const length = Array(N).fill(0); // arr[i]를 마지막으로 하는 LIS의 길이
length[0] = 1;

for (let i = 1; i < N; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
    length[i] = 1;
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
    length[i] = lis.length;
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
    length[i] = right + 1;
  }
}

console.log(lis); // [2, 5, 6, 7]
console.log(length); // [1, 2, 3, 1, 2, 4]
console.log(lis.length); // 최장 증가 부분 수열의 길이: 4

let result = [];
let count = lis.length; // 4
let index = N - 1; // 5

while (count > 0) {
  if (
    length[index] === count &&
    (result.length === 0 || result[result.length - 1] > arr[index])
  ) {
    result.push(arr[index]);
    count--;
  }

  index--;
}

console.log(result.reverse()); // [3, 5, 6, 7]

Example

  • 1965번: 상자넣기

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs").readFileSync(path).toString().split("\n");
const n = Number(input[0]); // 상자의 개수, 1 <= n <= 1_000
const arr = input[1].split(" ").map(Number); // arr[i]: 각 상자의 크기, 1 <= arr[i] <= 1_000

const lis = [arr[0]];

for (let i = 1; i < n; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      const mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
  }
}

console.log(lis.length);

  • 2631번: 줄세우기

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs").readFileSync(path).toString().split("\n");
const N = Number(input[0]); // 아이들의 수, 2 <= N <= 200
const arr = [];

for (let i = 1; i <= N; i++) {
  arr.push(Number(input[i]));
}

const lis = [arr[0]];

for (let i = 1; i < N; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
  }
}

console.log(N - lis.length);

참고 자료

Algorithms
algorithm
This post is licensed under CC BY 4.0 by the author.