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

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

최장 증가 부분 수열은 말 그대로 수열의 부분 수열 중에 가장 길이가 긴 것을 구하는 문제이다.

최장 증가 부분 수열을 푸는 방법은 크게 3가지로 분류된다.

1. 무식하게 풀기 - 완전탐색 (재귀)

2. dp 풀이 - 메모이제이션을 활용

3. 이분탐색을 활용한 풀이 -  LIS(k): 길이가 k인 LIS 중 마지막 수가 최소인 수를 저장

## 각각의 시간복잡도는 어떻게 될까?

1. 완전탐색  --------> O(2^N)

2. dp          --------> O(N^2)

3. 이분탐색 --------> O(NlogN)

 

개념이 계속 헷갈려서 각각의 방법을 활용하여 직접 java 코드로 구현해보았다.

아래의 java 코드를 함께 보면서 알아보도록 하자.

( 1번과 2번은 아이디어가 크게 다르지 않다.)

 

1번

/*
    * O(2^N) 풀이
    * 재귀 - 완전 탐색을 이용한 풀이
    * i번째 수를 넣는 경우/ 안 넣는 경우
    * */
    private static int LIS_BRUTEFORCE(int[] nums, int depth, List<Integer> tmp){
        if(depth == nums.length){
            return tmp.size();
        }
        int ans = -1;
        if(tmp.isEmpty()){
            tmp.add(nums[depth]);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
            tmp.remove(tmp.size() - 1);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
        }

        else if(nums[depth] > tmp.get(tmp.size() - 1)){
            tmp.add(nums[depth]);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
            tmp.remove(tmp.size() - 1);
        }
        else{
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
        }
        return ans;
    }

 

---

2번

DP테이블을 잡는 것이 중요했는데,단순히 DP[K] = 0 ~ K까지의 LIS라고 하는 것이 아니라 ,DP[K] = 0 ~ K까지 LIS 중 K번째 수를 마지막에 사용한 LIS의 최댓값으로 잡는다.

/*
    * O(N^2)
    * DP를 이용한 풀이
    * dp[k] : 1 ~ k 까지 중 k 번째 숫자를 마지막에 사용한 LIS
    * */
    private static int LIS_DP(int[] nums) {

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        Arrays.sort(dp);
        return dp[nums.length - 1];
    }

---

제일 중요한 3번!

이분탐색을 이용한 풀이로, 중요한 점은 배열을 하나 만들고 (dp[])

'길이가 k인 LIS 중 가장 마지막 원소가 최소'가 되는 값을 기록하면서 문제를 해결해야한다.

dp[k] = 길이가 k인 LIS 중 '가장 마지막 원소가 최소'인 값

 

ex) 주어진 수열 => [10 20 30 11 12 13 14]

최초에 dp는 INF로 초기화 시킨다. dp[] = [INF, INF, INF, INF, INF, INF, INF]

첫번째 루프 : dp[] = [10, INF, INF, INF, INF, INF, INF]

두번째 루프 : dp[] = [10, 20, INF, INF, INF, INF, INF]

세번째 루프 : dp[] = [10, 20, 30, INF, INF, INF, INF]

네번째 루프 : dp[] = [10, 11, 30, INF, INF, INF, INF]

★지금까지 길이가 2인 LIS를 찾아보면 (10, 20), (10, 30), (10, 11), (20, 30) 인데,

두번째 루프에서 dp의 두번째 원소가 20으로 채워졌으므로 20보다 큰 값은 들어가는게 손해이다.

따라서 계속 보다 작은 값이 나오면 갱신을 시켜줘야하므로 위에 작성한 만족하는 LIS 중 (10, 11)으로 갱신시켜야 한다.

따라서 네번째 루프의 두번째 값을 11로 갱신시켜야 한다.

-> 여기에서 이분탐색의 개념이 등장

 

최장 증가 부분 수열은 값이 이전보다 커질때 갱신하므로 dp테이블의 왼쪽 원소는 오른쪽 원소보다 작을 수 밖에 없다. 

즉, 정렬되어 있음.

 

nums[i] 값을 탐색 중이라면, dp테이블에서 nums[i]보다 큰 값중 가장 작은 값을 찾아서 값을 갱신시켜야 한다!

이분 탐색 시 left / right 는 조건에 만족하도록 조정하면서 while문 진행

+1 or -1 여부는 조건에 만족하는지 안 하는지로 결정

st, en은 조건에 만족하는 값의 범위로 while문에 넣어야함. (만족하지 않는 조건시, +1/-1로 조정)

추가))) mid값을 구할 때,  (st + en) / 2 보다 st + (en - st) / 2를 사용하자. -> 오버플로우 가능성

/*
    * O(NlogN)
    * 이분탐색을 이용한 풀이
    * dp[k] : 길이가 k인 LIS 중 '가장 마지막 원소가 최소'가 되는 값을 기록한다.
    * 이분탐색 시 mid 값은 st, en은 조건에 만족하도록 조정하면서 while문을 진행해야함.
    * ex) 조건에 만족하고 찾는 값이 왼쪽에 있다면 en = mid
    * ex) 조건에 만족하지 않고 찾는 값이 오른쪽에 있다면 st = mid + 1 
    *  *** +1 여부는 조건에 만족하는지 안 하는지 여부로 결정 ***
    * */
    private static int LIS_BINARY_SEARCH(int[] nums){
        int ret = 0;
        int[] dp = new int[nums.length ];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {

            //dp테이블에서 채워진 값들을 탐색하며 갱신한다.
            int st = 0;
            int en = nums.length;

            while(st != en){
                int mid = st + (en - st) / 2;
                //조건에 만족하고 찾는 값은 왼쪽에 있음
                if(dp[mid] >= nums[i]) en = mid;
                //조건에 만족하지 않고 찾는 값은 오른쪽에 있음
                else st = mid + 1;
            }
            //nums : 10 20 30 11 12 13 14
            //nums[i]: 11
            //dp   : 10 20 30 INF INF INF INF
            //dp   : 10 11 30 INF INF INF INF
            dp[st] = Math.min(dp[st], nums[i]);

            //찾아진 index 중 가장 큰 것들 갱신하며 저장
            ret = Math.max(ret, st);
        }
        return ret + 1;
    }

 

---

전체코드

import java.io.*;
import java.util.*;

/*
* LIS의 풀이법 해결과정
* 1. 완전탐색 -> 입력 문자열에 부분 문자열을 모두 구하여 가장 긴 것을 고른다. 2^n
* 2. 메모이제이션 활용 - dp
* 3. 이분 탐색
* */
public class LIS {

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

        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
//        int ans = LIS_BRUTEFORCE(nums, 0, new ArrayList<>()); //완전탐색을 이용한 풀이 O(2^N)
//        int ans = LIS_DP(nums); //dp를 사용한 풀이  O(N^2)
        int ans = LIS_BINARY_SEARCH(nums);
        System.out.println(ans);
    }

    /*
    * O(NlogN)
    * 이분탐색을 이용한 풀이
    * dp[k] : 길이가 k인 LIS 중 '가장 마지막 원소가 최소'가 되는 값을 기록한다.
    *
    * 이분탐색 시 mid 값은 st, en은 조건에 만족하도록 조정하면서 while문을 진행해야함.
    * ex) 조건에 만족하고 찾는 값이 왼쪽에 있다면 en = mid
    * ex) 조건에 만족하지 않고 찾는 값이 오른쪽에 있다면 st = mid + 1 
    *  *** +1 여부는 조건에 만족하는지 안 하는지 여부로 결정 ***
    * */
    private static int LIS_BINARY_SEARCH(int[] nums){
        int ret = 0;
        int[] dp = new int[nums.length ];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {

            //dp테이블에서 채워진 값들을 탐색하며 갱신한다.
            int st = 0;
            int en = nums.length;

            while(st != en){
                int mid = st + (en - st) / 2;
                //조건에 만족하고 찾는 값은 왼쪽에 있음
                if(dp[mid] >= nums[i]) en = mid;
                //조건에 만족하지 않고 찾는 값은 오른쪽에 있음
                else st = mid + 1;
            }
            //nums : 10 20 30 11 12 13 14
            //nums[i]: 11
            //dp   : 10 20 30 INF INF INF INF
            //dp   : 10 11 30 INF INF INF INF
            dp[st] = Math.min(dp[st], nums[i]);

            //찾아진 index 중 가장 큰 것들 갱신하며 저장
            ret = Math.max(ret, st);
        }
        return ret + 1;
    }

    /*
    * O(N^2)
    * DP를 이용한 풀이
    * dp[k] : 1 ~ k 까지 중 k 번째 숫자를 마지막에 사용한 LIS
    * */
    private static int LIS_DP(int[] nums) {

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        Arrays.sort(dp);
        return dp[nums.length - 1];
    }

    /*
    * O(2^N) 풀이
    * 재귀 - 완전 탐색을 이용한 풀이
    * i번째 수를 넣는 경우/ 안 넣는 경우
    * */
    private static int LIS_BRUTEFORCE(int[] nums, int depth, List<Integer> tmp){
        if(depth == nums.length){
            return tmp.size();
        }
        int ans = -1;
        if(tmp.isEmpty()){
            tmp.add(nums[depth]);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
            tmp.remove(tmp.size() - 1);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
        }

        else if(nums[depth] > tmp.get(tmp.size() - 1)){
            tmp.add(nums[depth]);
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
            tmp.remove(tmp.size() - 1);
        }
        else{
            ans = Math.max(ans, LIS_BRUTEFORCE(nums, depth + 1, tmp));
        }
        return ans;
    }
}