[백준] #11053 - 가장 긴 증가하는 부분 수열

🔒문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

---

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

---

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

🔑해결 아이디어

해당 문제는 LIS(Longest Increasing Subsequence) 문제로, DP로 해결할 수 있습니다.
문제 해결 $O(n^2)$의 시간복잡도를 가지는 해결방법과, 같은 방식에서 시간 복잡도를 $O(n(log n))$의 시간복잡도로 발전시킨 방법이 있습니다.

💻소스코드

함수 호출 코드

public static void main(String[] args) {  
    Scanner sc = new Scanner(System.in);  
    int len = sc.nextInt();  
    int[] array = new int[len];  
    for (int i = 0; i < len; i++) {  
        array[i] = sc.nextInt();  
    }  
    int ans = On2(array);  
    System.out.println(ans);  
}

O(n^2) 함수

public static int On2(int[] array){  
    int[] DP = new int[array.length];  
    DP[0] = 1;  
    int max = 1;  
    for (int i = 1; i < array.length; i++) {  
        int num = array[i];  
        int arrayMax = 0;  
        int indexMax = 0;  
        int dpMax = 0;  
        for(int j = 0; j<i; j++){  
            if(array[j] < num && DP[j] > dpMax){  
                arrayMax = array[j];  
                indexMax = j;  
                dpMax = DP[j];  
            }  
        }  
        DP[i] = dpMax + 1;  
        if(max < DP[i])  
            max = DP[i];  
  
    }
    return max;
}

$O(n^2)$ 방법에서 사용되는 DP값은 해당 index에서의 값으로 끝날 수 있는 LIS의 길이 입니다.
예시로 입력된 [10, 30, 20, 30, 10, 40]의 배열 입력을 봅시다.
DP[0]의 값은 0번째 index의 값으로 끝나는 LIS의 길이이므로, 1 입니다.
DP[1]의 값은 1번째 index의 값, 즉 30으로 끝나는 LIS의 길이이고, 이 때의 LIS는 [10, 30] 이므로 2 입니다.
이와 같은 방식으로 DP의 값을 전부 채우게 되면 DP는 [1, 2, 2, 3, 1, 4]이 됩니다.

이러한 DP배열을 만들기 위한 과정은 다음과 같습니다.

1. $i$ 번째 단계에선 입력배열의 $i$ 번째에 위치한 수num을 가져온다.
2. DP배열과 입력배열에서 $i-1$ 번째 값까지 탐색하며 다음을 확인한다.
   1. 입력배열의 $j$ 번째 값이 num 보다 작은 값인가.
   2. 1을 만족하는 index 중 DP배열에서 $j$ 이전의 값보다 큰 값이 없었는가.
3. DP의 $i$ 번째 값은 2에서 구한 $j$ 번째 값 + 1을 넣는다.
   1. 이 때 2에서 구한 값이 존재하지 않는다면 $i$ 번째 DP값은 1이다.

한마디로, 이전까지 구한 모든 부분수열 중 이번 값을 마지막으로 붙일 수 있는 가장 긴 수열을 찾아 해당 수열의 마지막에 이번 값을 붙인다고 생각하면 된다.

O(nlog(n))함수

public static int Onlogn(int[] array){  
    int[] subDP = new int[array.length];  
    //i-1 길이의 부분수열 중 가장 작은 끝나는 값  
    int subDPLen = 1;  
  
    subDP[0] = array[0];  
    for(int i = 1; i<array.length; i++){  
        int j = 0;  
        for(; j<subDPLen; j++){  
            if(array[i] <= subDP[j])  
                break;  
        }  
        if(j == subDPLen)  
            subDP[subDPLen++] = array[i];  
        else{  
            subDP[j] = array[i];  
        }  
    }  
  
    return subDPLen;  
}

$O(nlog(n))$의 방법으로 성능이 향상될 수 있는 핵심 아이디어는 DP[i]번째 값의 업데이트를 위해 i-1개의 이전 값을 모두 탐색해야 하는가 입니다.
i번째 입력에 대해 i-1개의 값을 탐색하지 않게 하기 위해 이번에는 DP에 다른 값을 저장하겠습니다.
이번에 사용할 DP의 값은 최대 i-1 길이를 가지는 부분배열의 끝나는 숫자 중 최솟값 입니다.

이번에도 역시 예시로 입력된 [10, 30, 20, 30, 10, 40]의 배열 입력을 이용해 DP 값을 계산해 봅시다.

첫번째 10이 입력이 되었습니다. 이 경우, LIS는 최대 길이가 1이며, 이 때 1의 길이를 가지는 LIS의 끝나는 숫자 중 최솟값은 10 입니다.
즉, DP[1]은 10 입니다.

두번째 30이 입력되었습니다.
1의 길이를 가지는 LIS는 [10], [30]이므로, DP[1]은 여전히 10 입니다.
2의 길이를 가지는 LIS는 [10, 30] 입니다. 그러므로, DP[2]는 30 입니다.

세번째 20이 입력되었습니다.
DP[1]은 여전히 10입니다.
2의 길이를 가지는 LIS는 [10, 30], [10, 20] 입니다.
즉, DP[2]의 값은 20으로 업데이트 됩니다.

왜 DP에 이런 값을 저장할까요?
다음 입력값 $n$이 입력된 경우를 가정해봅시다.
DP에서 $n$보다 큰 값을 저장하고 있는 index가 있다면, 이젠 해당 길이를 가지는 LIS는 더 작은 $n$의 값으로 끝나게 될것입니다.
$n$값보다 작은 값을 저장하고 있는 index $i$가 있다면, $i+1$의 길이를 가지는 LIS는 바로 직전 LIS의 뒤에 n을 추가하여 만들 수 있습니다.
이러한 DP배열을 만들게 된다면, 우리가 구하고자 했던 LIS의 길이는 DP배열이 가지고 있는 마지막 index값과 같을 것입니다.

DP배열의 업데이트 방법은 다음과 같습니다.
(구현 코드에서는 DP 배열의 시작 index가 1이 아니라 0임을 고려해 다음 설명을 읽어주세요!)

1. 입력 배열에서 $i$ 번째 원소 num 를 확인한다.
2. DP 배열의 값 중 num 보다 큰 index를 탐색한다.
3. DP값을 다음과 같이 갱신한다.
   1. 현재 DP 배열의 길이 안에서 index 값을 탐색하였다면, 해당 index의 값을 num 으로 교체한다. (즉, 이제는 index-1 길이를 가지는 LIS는 더 작은 값으로 끝나게 된다. )
   2. 현재 DP 배열 안에서 index값이 존재하지 않았다면 (즉, num이 $i$ 개의 원소 중 최댓값이라면 ) DP배열의 크기를 늘려 마지막 index의 값으로 num 을 저장한다.
4. DP 배열의 마지막 index 값 + 1 이 곧 LIS 길이이다.