limecats

LIS

@limecats · August 16, 2022 · 12 min read
LIS

SERIES: Algorithm (5)

LIS(최장 증가 부분 순열)

개념

어떠한 순열이 주어졌을 때, 그 수열에서 순서를 바꾸지 않고 일부 원소를 뽑아서 새로 만든 수열을 부분 수열이라고 한다. 이 수열이 오름차순으로 되어 있으면 증가 부분 수열이 되는 것이다. 이렇게 만들어진 수열 중에 가장 긴 수열을 LIS(촤장 증가 부분 순열) 이라고 한다.

예시

4 2 1 3 5 8 6 7

위와 같은 순열이 주어졌을 때,LIS는 다음과 같다.

2 3 5 6 7

알고리즘

DP 활용 (N2N^2)

dp[i]는 arrs[i]를 마지막으로 하는 최장 길이의 순열로 설정하였다. 이때, 0부터 N까지 탐색을 하면서 N 미만의 arrs[i] 보다 작으면서 dp가 가장 큰 값에 +1을 해주면 된다.

따라서, 다음과 같은 반복으로 탐색한다.

for (int i = 0; i < N ; i++){
	for (int j = 0; j < i ; j++){
		if(arrs[j] <= arrs[i] && dp[i] <= dp[j]){
			dp[i] = dp[j];
		}
	}
	dp[i] += 1;
}

이렇게 탐색하면 다음과 같은 결과가 나온다.

--- 0 1 2 3 4 5 6 7
arrs 4 2 1 3 5 8 6 7
dp 1 1 1 2 3 4 4 5

여기서 최장 수열의 길이는 가장 큰 값인 5가 된다.

이분 탐색 활용 (NlogNNlogN)

하지만 배열의 원소를 탐색하면서 그 전의 모든 원소를 모두 탐색하기 때문에 O(N2N^2)의 시간 복잡도를 가진다. 그래서, N이 커짐에 따라서 시간이 매우 오래 걸린다.

여기서 이전의 원소를 탐색하는 과정에 이분탐색을 활용해서 O(logNlogN)으로 줄인다면 O(NlogNNlogN)로 줄일 수 있다.

여기서 중요한 컨셉이 하나 있다. 같은 길이의 수열이라면 최고값이 작어야 뒤의 수열을 만들기 좋다는 것이다. 위의 수열로 설명하자면 만약 6까지 탐색을 완료했다고 생각해보자 그렇다면 만들 수 있는 최장 수열의 끝은 2가지가 있다.

---- 0 1 2 3
arr1 1 3 5 6
arr2 1 3 5 8

여기서 마지막으로 들어갈 수 있는 원소는 6과 8이 있다. 하지만 8이되면 다음으로 9가 들어온다면 수열을 이어갈 수 있지만 7이 온다면 수열을 이어갈 수 없다. 그래서 뒤에 어떤 숫자가 모른다는 전제하에 같은 길이의 수열이라면 가능한 수 중에 가장 작은 수를 골라야 한다.

그래서 탐색하면서 min이라는 배열인 min[n]에 길이가 n인 증가 부분 수열의 최소 값을 넣어주면서 갱신한다.

위의 예시를 사용해서 어떤 식으로 진행되는지 한번 보도록 하자.

  1. i == 1
--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 4

첫 원소임으로 첫 값을 그냥 넣어준다.

  1. i == 2

마지막 원소가 4임으로 2를 연장해서 길이를 늘릴 수 없다. 하지만 길이가 1인 배열의 마지막 값보다 작음으로 2로 바뀔 수 있다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 2
  1. i == 3

이전과 마찬가지로 연결해서 늘릴 수는 없고 길이가 1인 배열의 최소값보다 작음으로 바뀔 수 있다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1
  1. i == 4

여기서는 여태까지 만들어진 최장 수열의 마지막 수보다 크기 때문에 바로 연결해서 길이를 늘릴 수 있다. 그래서 min 배열에 추가해준다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3
  1. i == 5

min 배열의 맨 끝에 있는 원소보다 큼으로 더해서 연장해준다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3 5
  1. i == 6

min 배열의 맨 끝에 있는 원소보다 큼으로 더해서 연장해준다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3 5 8
  1. i == 7

min 배열의 맨 끝보다 작은 원소임으로 교환할 위치를 찾아야 한다. min[n-1] 보다 크고 min[n] 보다 작은 n의 위치로 교환을 하는데, 여기서는 n == 4 인 위치이다.

이때, min 배열은 오름차순으로 정렬되어 있기 때문에 이분 탐색을 이용하면 탐색에 필요한 횟수를 logNlogN 로 줄일 수 있다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3 5 6
  1. i == 8

마지막으로 배열의 마지막 수보다 큼으로 연장해서 끝이 난다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3 5 6 7

길이 구하기

이 연산으로 min 배열의 크기가 최장 증가 부분 수열의 크기가 된다.

수열 구하기

하지만 여기서 유의해야할 점이 min 배열이 LIS를 의미하지 않기 때문에 LIS를 직접 구하기 위해서는 별도의 추가적인 방법이 필요하다.

그 방법은 min 배열에 넣을 때 몇번째 인덱스에 집어넣는지 저장하는 방법이다.

--- 1 2 3 4 5 6 7 8
arrs 4 2 1 3 5 8 6 7
min 1 3 5 6 7
record 1 1 1 2 3 4 4 5

record 배열에는 arrs 값이 min 배열에 들어갈때 몇 번째 인덱스로 들어가는지 기록한다. 뒤에서 부터 가장 큰수에서 1씩 빼면서 제일 가까운 수를 사용해서 실제 LIS 배열을 찾을 수 있다.

코드

길이 구하기

import java.util.*;

public class LIS {
    public static void main(String[] args) throws Exception {
        int[] arrs = {4, 2, 1, 3, 5, 8, 6, 7};
        int[] min = new int[8];

        int minIdx = 0;
        min[0] = arrs[0];

        for (int i = 1; i < 8; i++) {
            if (min[minIdx] < arrs[i]) {
                min[minIdx + 1] = arrs[i];
                minIdx += 1;
            } else {
                int change = Arrays.binarySearch(min, 0, minIdx, arrs[i]);
                if (change < 0) {
                    change = -(change + 1);
                }
                min[change] = arrs[i];
            }
        }

        System.out.println(Arrays.toString(arrs));
        System.out.println(Arrays.toString(min));
        System.out.println(minIdx + 1);
    }
}

LIS 구하기

import java.util.Arrays;

public class LISTest {
    public static void main(String[] args) throws Exception {
        int[] arrs = {4, 2, 1, 3, 5, 8, 6, 7};
        int[] min = new int[8];
        int[] record = new int[8];

        int minIdx = 0;
        min[0] = arrs[0];

        for (int i = 1; i < 8; i++) {
            if (min[minIdx] < arrs[i]) {
                min[minIdx + 1] = arrs[i];
                minIdx += 1;
            } else {
                int change = Arrays.binarySearch(min, 0, minIdx, arrs[i]);
                if (change < 0) {
                    change = -(change + 1);
                }
                min[change] = arrs[i];
            }
            record[i] = minIdx;
        }

        int[] LIS = new int[minIdx + 1];
        int count = minIdx;
        int countLIS = minIdx;
        for (int i = 7; i >= 0; i--) {
            System.out.println(count);
            if (record[i] == count) {
                LIS[countLIS] = arrs[i];
                countLIS -= 1;
                count -= 1;
            }
        }

        System.out.println(Arrays.toString(arrs));
        System.out.println(Arrays.toString(min));
        System.out.println(Arrays.toString(record));
        System.out.println(Arrays.toString(LIS));
        System.out.println(minIdx + 1);

    }
}

마치며

정확히 LIS구할 때 사용하는 배열이 무엇을 뜻하는지 모른채로 알고리즘 설명만 있는 글들이 많아서 이해하기가 어려웠다.

만약 레퍼런스의 블로그를 찾지 못했다면 아직도 검색하고 있었을 것이다...

내가 글을 잘 쓰는 편은 아니지만 나 나름대로 최대한 이해하기 쉽게 풀어쓰려고 노력했고, 처음 봤던 블로그의 주소도 남겨뒀으니 비슷하게 이해가 안되는 사람들에게 도움이 되었으면 좋겠다.

Reference

[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)

Previous Post
Next Permutation
Next Post
StringFormat
@limecats
내 생각을 정리해보자