[Algorithm] LIS 알고리즘 (최장증가수열 알고리즘)

LIS 알고리즘이란?

LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 

풀이

1. DP로 풀기 

시간 복잡도 O(N^2) 이기 때문에 원소의 개수가 작은 경우에는, 해당 방법으로 문제를 풀 수 있다.

{10 20 10 30 20 50}

수열

1	2	3	4	5	6
10	20	10	30	20	50

 

DP[i] = i번째 원소를 포함하는 증가 수열의 최대 원소 개수

N=1

1	2	3	4	5	6
1

 

N=2

1	2	3	4	5	6
1	2

현재 index의 원소 값과, 그 미만의 index의 원소 값을 비교

현재 원소보다 작은 원소가 있다면 해당 index의 dp값 중 최대값에 + 1을 한 것이 현재 dp[i] 의 값이 된다.

20보다 작은 값이 10이 있으며 10의 dp값은 1이므로, dp[2] = 2가 된다. 

 

N=3

1	2	3	4	5	6
1	2	1

3번 인덱스의 경우, 이전 원소에서 10보다 작은 원소가 없다. 그러므로 dp[3] =1 이 됨.

 

N=4

1	2	3	4	5	6
1	2	1	3

1, 2, 3 모두 4번 인덱스 값인 30보다 작은 원소들이다. 

이중 dp값의 최대는 dp[2]= 2이므로 dp[4] = 3이 됨.

 

N=5

1	2	3	4	5	6
1	2	1	3	2

20보다 작은 값은 1, 3번 인덱스며 최대값은 1이므로 dp[5]= 2이다.

 

N=6

1	2	3	4	5	6
1	2	1	3	2	4

50보다 작은 원소값이면서 dp값의 최대는 dp[4] = 3이므로 여기에 1을 더한 값이 dp[6] = 4가 된다.

 

2021.10.31 - [Problem Solving/BOJ] - [BOJ 11053] 가장 긴 증가하는 부분 수열 (Java)

 

[BOJ 11053] 가장 긴 증가하는 부분 수열 (Java)

 

2. 이분탐색을 이용해서 풀기 (Lower Bound)

DP로 풀면 이중 for문을 돌기 때문에 시간 복잡도가 O(N^2)이며, 원소의 개수가 많은 경우 답을 구하기 어렵다. 

이분 탐색을 이용해서 최장 길이를 구할 수 있는 방법이 있다. 수열을 순회하면서 현재 값을 신규 배열에 넣거나 치환하는 방식으로 구현되며, 현재 값의 lowerbound가 없다면 삽입하고 lowerbound값이 있다면 해당 값을 찾아서 치환한다. 해당 방식으로 최장 길이만 구할 수 있으므로, 실제 LIS 수열을 구하기 위해서는 따로 역추적 과정을 거쳐야 한다.

(참고)
LowerBound는 타겟 값 이상의 값이 나오는 처음 위치
UpperBound는 타겟 값을 초과하는 값이 나오는 처음 위치

 

대표문제

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

1	2	3	4	5	6
10	20	10	30	20	50

 

N=1

10

일단 첫 번째 원소를 넣는다. 

 

N=2

10

20

LIS배열에 마지막 원소가 현재 원소보다 작다면 lowerbound를 찾을 수 없으므로 그대로 값을 넣는다. 

 

N=3

10

20

LIS배열에 lowerbound 를 찾아서 해당 값으로 치환한다.

 

N=4

10

20

30

삽입

 

N=5

10

20

30

치환

 

N=6

10

20

30

50

삽입

 

해당 배열의 길이가 최장 길이가 된다.

값을 치환 하는 이유? 

ex) 10 5 7 15 

10 보다 5가 더 작기 때문에 값을 치환해줘야 그 다음 원소가 7이 5를 참조할 수 있다. 

 

소스코드

package lis;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ12015 {

    public static int N;
    public static int[] lis;
    public static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 수열, LIS 저장할 배열 초기화
        lis = new int[N+1];
        arr = new int[N+1];

        //수열 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int lisIdx = 1;
        // 첫 번째 원소를 넣는다.
        lis[lisIdx] = arr[1];

        // 수열을 순회하면서 lowerbound 값을 찾는다.
        for(int i = 2; i <= N; i++){
            // lis의 마지막 원소가 현재값 보다 작다면,
            // lis에는 현재 값의 lowerbound가 존재하지 않는다. 그러므로 그대로 넣어준다.
            if(lis[lisIdx] < arr[i]){
                lisIdx++;
                lis[lisIdx] = arr[i];
            } else {
               // lis배열에서 arr[i]의 lowerbound값에 해당하는 index를 찾는다.
               int idx = lowerbound(1, lisIdx, arr[i]);
               // 현재 값으로 치환
               lis[idx] = arr[i];
            }
        }
        System.out.println(lisIdx);

    }

    public static int lowerbound(int L, int R, int n){
        int mid = 0;
        while(L < R){
            mid = (L+R)/2;
            if(n <= lis[mid]) R = mid; // n 이상 값을 포함해야하므로 mid+1이 아니라 mid값을 취한다.
            else L = mid + 1;
        }
        return L;
    }
}

 

3. LIS 수열 구하기

앞서 이분 탐색으로 최장 길이를 구할 수는 있지만, 이를 구성하는 수열을 정확히 알 수는 없다. 

예를 들어 {10 20 30 5 25} 수열을 위 방식으로 lowerbound를 찾아 치환한 결과는 {5, 20, 25} 이다. 

실제 답은 {10, 20, 30} 또는 {10, 20, 25} 가 되어야 한다. LIS 수열 자체를 구하기 위해서는 입력받은 수가 어떤 index에 들어가는지 정보를 저장해서 역추적 하는 과정이 필요하다. 

 

 

대표문제

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

역추적을 위해서는 현재값을 신규 배열에 삽입하거나 lowerbound를 찾아서 치환하는 작업을 할 때 

신규 배열에 어떤 index에 값이 들어가는지 알아야 한다. 

 

N=1

1	2	3	4	5	6
10	20	10	30	20	50
1

10

일단 첫 번째 원소를 넣는다. 

 

N=2

1	2	3	4	5	6
10	20	10	30	20	50
1	2

10

20

LIS배열에 마지막 원소가 현재 원소보다 작다면 lowerbound를 찾을 수 없으므로 그대로 값을 넣는다. 

 

N=3

1	2	3	4	5	6
10	20	10	30	20	50
1	2	1

10

20

LIS배열에 lowerbound 를 찾아서 해당 값으로 치환한다.

 

N=4

1	2	3	4	5	6
10	20	10	30	20	50
1	2	1	3

10

20

30

삽입

 

N=5

1	2	3	4	5	6
10	20	10	30	20	50
1	2	1	3	2

10

20

30

치환

 

N=6

1	2	3	4	5	6
10	20	10	30	20	50
1	2	1	3	2	4

10

20

30

50

삽입

---

 

역추적 과정

배열에 마지막부터 순회를 하면서, 신규 배열에 마지막으로 들어간 숫자를 찾는다. 

그 이전에 들어간 숫자를 찾는다 (반복)

배열 순회가 끝나면 아래의 숫자들이 Stack에 들어간 것을 확인할 수 있다.

	1	2	3	4	5	6
arr	10	20	10	30	20	50
loc	1	2	1	3	2	4

 

        // 역추적
        Stack<Integer> stack = new Stack<Integer>();
        int index = lisIdx;
        for(int i = N; i >= 1; i--){
            if(loc[i] == index){
                index--;
                stack.push(arr[i]);
            }
        }
        while(!stack.isEmpty()){
            bw.write(stack.pop() + " ");
        }
        bw.flush();

소스코드

package lis;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;


public class BOJ14003 {

    public static int N;
    public static int[] lis;
    public static int[] arr;
    public static int[] loc;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        // 수열, LIS 저장할 배열 초기화
        lis = new int[N+1];
        arr = new int[N+1];
        loc = new int[N+1];

        //수열 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int lisIdx = 1;
        // 첫 번째 원소를 넣는다.
        lis[lisIdx] = arr[1];
        loc[1] = lisIdx; // lis에 i번째 수가 들어갔을 때 어떤 index에 들어갔는지 넣어준다.

        // 수열을 순회하면서 lowerbound 값을 찾는다.
        for(int i = 2; i <= N; i++){
            // lis의 마지막 원소가 현재값 보다 작다면,
            // lis에는 현재 값의 lowerbound가 존재하지 않는다. 그러므로 그대로 넣어준다.
            if(lis[lisIdx] < arr[i]){
                lisIdx++;
                lis[lisIdx] = arr[i];
                loc[i] = lisIdx; // lis에 i번째 수가 들어갔을 때 어떤 index에 들어갔는지 넣어준다.
            } else {
                // lis배열에서 arr[i]의 lowerbound값에 해당하는 index를 찾는다.
                int idx = lowerbound(1, lisIdx, arr[i]);
                // 현재 값으로 치환
                lis[idx] = arr[i];
                loc[i] = idx; // lis에 i번째 수가 들어갔을 때 어떤 index에 들어갔는지 넣어준다.
            }
        }
        bw.write(lisIdx + "\n");

        // 역추적
        Stack<Integer> stack = new Stack<Integer>();
        int index = lisIdx;
        for(int i = N; i >= 1; i--){
            if(loc[i] == index){
                index--;
                stack.push(arr[i]);
            }
        }
        while(!stack.isEmpty()){
            bw.write(stack.pop() + " ");
        }
        bw.flush();
    }

    public static int lowerbound(int L, int R, int n){
        int mid = 0;
        while(L < R){
            mid = (L+R)/2;
            if(n <= lis[mid]) R = mid; // n 이상 값을 포함해야하므로 mid+1이 아니라 mid값을 취한다.
            else L = mid + 1;
        }
        return L;
    }
}