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

Concept

• 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
• 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은

• 1,3,5
• 1,3,4
• 3,5
• 1,2,4
• 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3

---

Feature

이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다.

LIS의 길이를 구하는 최적 방법에는 2가지가 있다.

• 다이나믹 프로그래밍(DP)를 활용한 방법
  • 이중 for문을 활용하여 시간복잡도 : O(N^2)
• 이분탐색을 활용한 방법
  • 시간복잡도 : O(NlogN)

---

Implement

Dynamic Programming

• DP로 풀이하는 방식에는 상향식(Bottom-up), 하향식(Top-Down) 두 가지 방식이 있는데 이번 포스팅에서는 상향식 방식에 대해 설명.
  • 상향식 : 작은 문제를 모아 큰 문제를 해결 (for문으로 구현)

• 위 수열에서 각 인덱스 별로 최장 수열을 구하는걸 부분문제로 정의할 수 있음.
• 핵심은 각 인덱스를 최장 수열의 끝으로 정한 후 앞의 인덱스들을 참조해 각 인덱스의 LIS를 구하는 것.

1. 0번 인덱스(1)에서의 LIS는 1밖에 없으니 1
2. 1번 인덱스(3)에서의 LIS는 (1,3)으로 2
3. 2번 인덱스(2)에서의 LIS는 (1,2)로 2
4. .....

• 위와 같이 각 인덱스들의 LIS를 구한 것을 dp배열로 나타내면 아래와 같이 나타낼 수 있고, 이 중 최장 부분 수열의 길이는 3이라는걸 알 수 있음.

---

Source Code

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

public class Solution {
    static int N;
    static int[] arr, 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];
        arr = new int[N];

				//수열 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

				//상향식(Bottom-up) 방식 풀이
        for(int i=0; i<N; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1); //핵심 로직
                }
            }
        }
        int max = 0;
        for(int i=0; i<N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}

• 위의 소스코드에서 각 인덱스들의 최장 증가 부분수열의 길이의 초기값은 1로 초기화.
• 0 ~ i 까지의 앞부분 인덱스들을 비교하여 현재 i번째 인덱스의 값보다 작을 경우 dp[i]를 갱신
  • dp[i]와 dp[j]+1 (j번째 인덱스를 끝으로 하는 LIS의 길이에서 i번째 인덱스를 추가한 길이) 를 비교하여 최대값으로 갱신.

---

정리

• DP를 활용한 LIS알고리즘의 핵심 로직은 각 인덱스를 끝으로 두는 최장 증가 부분 수열을 구하는 것으로 for문을 돌면서 0~i까지의 i번째 인덱스의 앞쪽만 보고 구하는 것만 기억한다면 쉽게 풀이할 수 있음.
• 또한 이전 부분 문제의 해(dp[j])를 사용함으로 메모이제이션을 사용한다고 볼 수 있음.

---

Refference

기본문제

1. SWEA_3307. 최장 증가 부분 수열

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

SW Expert Academy

1. BOJ_11053 가장 긴 증가하는 부분 수열

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

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

 

응용문제

1. BOJ_2565 전깃줄

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

2565번: 전깃줄

 

이후 추가적으로 이분탐색을 활용한 LIS 알고리즘 추가할 예정.