LIS (Longest Increasing Subsequence)

• 최장 증가 부분 수열
• 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제

Brute Force 접근 방법

• 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지 판별한다
• 증가 수열 중 가장 길이가 긴 값을 구한다
• ex) S = {3, 2, 6, 4, 5, 1}
  • $2^6$ = 64개의 부분 집합
• 부분 집합 알고리즘을 활용
• O($2^n$) → 지수 시간 복잡도

DP 접근 방법

DP 접근 방법

• 입력 : 숫자 배열 $a_1, a_2, ..., a_n$
• LIS(i) = $a_1, a_2, ..., a_i$ 에서 최장 부분 수열의 길이
• LIS(i)를 LIS(1), LIS(2), …LIS(i-1)와의 관계로 표현 할 수 있을까?
• Case 1 : LIS(i)가 $a_i$를 부분 수열의 마지막으로 포함하지 않는다면, LIS(i) = LIS(i-1)
• Case 2 : LIS(i)가 $a_i$를 부분 수열의 마지막으로 포함한다면, LIS(i) = ?
  • 증가 수열의 관계인 $a_j$ < $a_i$ 인 $a_j$ 찾는다
  • j값을 알 수 없으므로 모두 검색해야 한다
  • 그 중 최대값을 찾아 1 증가시켜 LIS(i)에 저장한다
    • LIS (i) = 1 + max LIS(j)
    • j < i and $a_j$ < $a_i$
  • LIS(i) 중에서 최대값을 찾는다 (i : 1 ~ n)

DP 접근 알고리즘

• LIS[i] : i원소를 증가 부분 수열의 마지막으로 하는 증가 부분 수열의 최장 길이 값
• O($n^2$)

FOR i in 1 -> n
	LIS[i] = 1
	FOR j in 1 -> i-1
		IF a[j] < a[i] AND LIS[i] < LIS[j] + 1
			LIS[i] = LIS[j] + 1
RETURN mas LIS[]

• {3, 2, 6, 4, 5, 1}

LIS[1]	LIS[2]	LIS[3]	LIS[4]	LIS[5]	LIS[6]
1	1	{3, 6} : 2	{3, 4} : 2	{3, 4, 5} : 3	1

백준 11053 가장 긴 증가하는 부분 수열

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

public class Main {
    static int N, answer = 1;
    static int[] dp;
    static int[] num;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        num = new int[N];
        dp = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if(num[j] < num[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);
    }
}

DP : 이진 탐색 활용

• 이진 탐색을 이용한 보다 효율적인 방법
• C[k] : 길이 k의 증가 수열에 대하여 길이 k자리에 위치에 올 수 있는 가능한 값 중 가장 작은 값을 C[k]에 저장
• 각 원소마다 C[]를 갱신하기 위해 이진 탐색을 수행한다
• $O(nlogn)$

백준 12015 가장 긴 증가하는 부분 수열 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, num, answer, index;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        dp = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            num = Integer.parseInt(st.nextToken());
            index = lowerBound(num);
            if(dp[index] == 0) ++answer;
            dp[index] = num;
        }
        System.out.println(answer);
        br.close();
    }

    static int lowerBound(int num) {
        int low = 0;
        int height = answer;
        int mid;
        while(low < height){
            mid = (low + height)/2;
            if(dp[mid] < num)
                low = mid + 1;
            else
                height = mid;
        }
        return low;
    }
}