LIS(Longest Increasing Subsequence - 최장 증가 수열) 알고리즘

해당 알고리즘은 배열중 가장 긴 증가수열을 찾는 알고리즘이다

예를 들어

1

4

2

5

3

2

 

라는 배열이 있다고 가정해 보자

 

1		2		3
	4		5
					2

 

{1,2,3}, {4,5}, {2}중에서 가장 긴 증가수열을 찾으면 {1,2,3}이다.

 

 

이러한 문제를 해결하고자 나온 것이 LIS(Longest Increasing Subsequence - 최장 증가수열) 알고리즘이다.

기본적으로 DP를 사용하면 N^2이 걸리고 이분탐색사용 시 NlogN의 시간이 걸린다.

예시 코드)

for (int k = 0; k < n; k++){
	length[k] = 1;
    for (int i = 0; i < k; i++){
        if(arr[i] < arr[k]){
            length[k] = max(length[k], length[i] + 1);
        }
    }
}

length [i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미한다.

ex) length[4]=3

ex)length[3]=2

운용 문제)

2565번: 전깃줄

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

public class Main {
    public static int N;
    public static int[][] Line;
    public static int dp[];
    public static void solve(){
        Arrays.fill(dp,1);
        for(int i=0;i<N;i++)
            for(int j=0;j<i;j++)
                if(Line[i][1]>Line[j][1])
                    dp[i]=Math.max(dp[i], dp[j]+1);

        Arrays.sort(dp);
        System.out.println(N-dp[dp.length-1]);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        dp= new int[N];
        Line=new int[N][2];
        StringTokenizer st;
        for(int i=0;i<N;i++){
            st= new StringTokenizer(br.readLine());
            Line[i][0]=Integer.parseInt(st.nextToken());
            Line[i][1]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(Line, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        solve();


    }
}

가장 적은 전선제거=전체 전선-최대한 많이 설치할 수 있는 전선의 개수