[알고리즘][DP] 최장 증가 부분 수열(LIS)

1. 개념

1.1. 정의

부분 수열

• 주어진 수열 중 일부를 뽑아 새로 만든 수열
• 뽑아서 새로 만들더라도 전후 관계 순서는 유지

 

최장 증가 부분 수열(Longest  Increasing Sequence; LIS)

• 부분 수열의 원소 중 오름차순을 유지하면서도 길이가 가장 긴 수열

2. 구현

핵심 아이디어

• 전체 수열의 LIS 길이 == 각 숫자로 끝나는 LIS 길이 중 최댓값 구하기
• i번째 원소의 LIS 는 i번째 원소보다 작은 i-n번째 원소들의 LIS 값 중 최댓값에 + 1
• 모든 원소는 자기 자신을 증가 부분 수열로 가지고 있기 때문에 dp[i] = 1 로 초기화

 

 

   static int solution(int N, int[] sequence) {

        int[] dp = new int[N + 1]; // dp[i] : i번째 원소를 끝으로하는 LCS 길이

        int answer = 1;

        for (int i = 1; i <= N; i++){
            dp[i] = 1; // 최소 길이는 1
            for (int j = 1; j < i; j++){
                if (sequence[i] > sequence[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 이전 값 중 최장 길이 갱신
                    answer = Math.max(answer, dp[i]);
                }
            }
        }

        return answer;
    }

 

3. 활용

 

3.1. 가장 긴 바이토닉 수열 : 백준 11054

최장 증가 부분 수열과 최장 감소 부분 수열을 이용한 문제

 

최장 감소 부분 수열(Longest Decreasing Sequence; LDS)은 최장 증가 부분 수열을 역으로 진행하여 산출

 

3.2. 전깃줄 : 백준 2565

LIS 를 어떤 방식으로 활용 가능한지 인사이트를 제공해주는 문제.

 

4. 참고자료

 

위키백과 

 

코딩테스트 합격자 되기 : 파이썬 편