[알고리즘/JAVA] 동적 계획법(DP) : LIS (최장 증가 부분 수열)

https://en.wikipedia.org/wiki/Knapsack_problem

 

동적 계획법

 

최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법

주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다.

 

• Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.
• Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다.
  

 

동적 계획법(다이나믹 프로그래밍, DP)에 대한 자세한 설명은 아래의 포스팅을 살펴보자.

https://sjh9708.tistory.com/212

[알고리즘/JAVA] 동적 계획법(DP) : 이론과 활용 [+ 파도반 수열 / 1로 만들기 / 계단 오르기]

 

 

---

문제 : 가장 긴 증가하는 부분 수열 (백준 11053)

 

 

LIS(Longest increasing Subsequence)는 배열 또는 순차 데이터에서 순서를 유지하면서 값이 증가하는 부분 수열 중 가장 긴 것, 즉 값이 점점 커지는 가장 긴 부분 수열을 찾는 문제이다.

 

만약 배열의 각각의 원소들을 포함/제외의 경우의 수를 모두 따져보는 완전 탐색 기반일 경우 최악의 경우 2^1000의 경우의 수가 나올 것이므로 불가능하다.

 

10

20

10

30

20

50

 

위 문제의 예제 입력에 대한 LIS의 결과는 위 네개의 원소를 선택하는 경우, 4이다.

가만 보면 부분 문제의 해를 활용할 수 있을 것 같아 보인다. 인덱스가 6(50)일 때의 LIS는, 인덱스가 4(30)일 경우의 LIS인 3에 1을 더한 값이다. 이를 응용하여 규칙성을 한번 찾아보자.

 

 

 

---

동적 프로그래밍 : 규칙성 찾기

 

이제 수열을 길이가 1인 경우부터 시작해서 문제에서 주어진 길이까지 증가시켜가면서, 해당 케이스의 최댓값, 즉 부분 문제의 최적해를 구해나가 보면서 규칙성을 파악해보자.

 

 

 

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1

• 1번째 인덱스의 10 : 이전 원소가 존재하지 않으므로 부분해는 1이다.

---

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1	2

• 2번째 인덱스의 20 : 증가시킬 이전 원소, 즉 20보다 작은 이전 원소가 존재한다. 따라서 이전 원소의 최적 부분해인 1에서 현재 인덱스까지 포함시켜 1을 추가로 더해주어 2가 된다.
  
  

---

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1	2	1

 

• 3번째 인덱스의 10 : 증가시킬 이전 원소, 즉 10보다 작은 이전 원소가 존재하지 않는다. 따라서 해당 부분해는 1이다.

 

 

---

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1	2	1	3

• 4번째 인덱스의 30 : 증가시킬 이전 원소에 해당하는 30보다 작은 원소들이 세 개가 존재한다. 따라서 최적 부분해를 구하기 위해서는 이들 중 최대 이익이 되는 값을 뽑아야 하므로 2에서, 1을 추가로 더해 3이 부분해가 된다.

 

 

---

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1	2	1	3	2

• 5번째 인덱스의 20 : 조건에 맞는 이전 최적해가 두가지 케이스가 있었다. 둘 다 길이가 1이므로, 해당 인덱스의 최적해는 2가 된다.

 

 

---

0	1	2	3	4	5	6
0	10	20	10	30	20	50
0	1	2	1	3	2	4

• 6번째 인덱스의 50 : 이전 인덱스들의 값이 모두 50보다 작으므로 어디에서 이어도 사용할 수 있다. 즉 이전의 부분 최적해 중 최대 길이가 되는 값에서 이어붙여서 최적해를 구해야 한다. 따라서 최적해가 3이었던 수열에서 이어서 최종 길이는 4가 된다.

 

LIS[i] = max(LIS[j]) + 1 (j는 다음을 만족하는 모든 수 : j < i and A[i] > A[j])

 

---

코드 작성

 

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


public class Main {
    static Integer[] numbers;
    static Integer[] dp;


    static Integer lis(int n){
        if(dp[n] == null){
            dp[n] = 1;
            for(int i = n; i > 0; i--){
                if(numbers[i] < numbers[n]){
                    dp[n] = Math.max(lis(i) + 1, dp[n]);
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        numbers = new Integer[n + 1];
        dp = new Integer[n + 1];
        st = new StringTokenizer(br.readLine());
        
        numbers[0] = 0;
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        // 모든 dp[]를 채워야 한다.
        for(int i = 1; i <= n; i++){
            lis(i);
        }

        // 최대값 계산
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            max = Math.max(dp[i], max);
        }
        System.out.println(max);
    }
}

 

1. Top-down: calc() 함수를 통해서 배열에서 n번째 요소를 기준으로 LIS의 길이를 계산한다.
   1. dp[n]이 null이 아닐 경우 메모리제이션된 값을 이용한다.
   2. 만약 dp[n]이 null이면 기본값으로 1로 설정한다. 이후 인덱스가 현재 값보다 작은 배열의 원소에 대해 작은 값들을 찾아서, 부분해들의 후보군으로 삼는다. 후보군들 중 최대값과 1을 더하여 현재 인덱스의 부분 최적해로 삼는다.
2. 항상 마지막 인덱스가 포함된 해가 최적해라는 보장이 없다. 위의 Top-down 로직에서 dp 배열은 타겟 인덱스의 값보다 작은 값의 인덱스에 대해서만 값이 채워지므로, 반복문을 통해 전체 dp를 채우고, 그 중 최대값을 얻어내야 한다.

 

 

---

문제 : 가장 긴 증가하는 부분 수열 2 (백준 12015)

 

 

해당 문제는 위의 LIS 문제와 동일하지만, 수열의 크기 N을 주목하자. 100만개의 수열의 크기를 위의 로직처럼 반복문을 돌리게 되면 O(n^2)의 시간 복잡도에 의해서 1조번의 연산을 수행하게 되고, 이는 1억번의 연산보다 훨씬 아래로 나와야 하는 1초라는 시간제한에 걸리게 된다. 따라서 문제 풀이 방법을 개선할 필요가 있다.

 

 

 

---

LIS 개선

 

위에서는 LIS[i]를 계산하기 위해서 LIS[0] ~ LIS[i-1]를 다 훑어보아야 했다. 그런데 이것이 연산을 많이 수행한다는 것이 문제였다.

사실 결국 LIS[i]를 구하기 위해 필요했던 것은 [0 ~ i-1]에서 현재 값보다 작은 값들을 찾고, 그들의 최대 LIS 길이를 얻어내야 했던 것이다.

 

따라서 LIS 길이에 해당하는 메모리제이션 테이블을 만든 후, 해당 길이를 만들 수 있는 최소값을 기억하면서 사용하자는 아이디어를 낼 수 있다.

 

무슨 소리인지 이해가 되지 않는다면 아래의 과정을 한번 천천히 살펴보자.

 

 

---

 

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1

 

0	1
0	10

 

다음과 같이 길이에 대해서 메모리제이션 테이블을 만든다.

길이 1을 만족시키는 값들 중 최소값은 10이고, 앞으로 10보다 큰 값을 가지는 수에 대해서는 해당 길이가 추가적으로 더해질 것이다.

 

 

 

---

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2

 

0	1	2
0	10	20

 

다음 20에 대해서 작성해보자.
메모리제이션 테이블을 보니 20보다 작은 값이 있고, 그 길이는 1이다. 이 길이는 20 앞에 올 수 있는 증가 수열의 최대 길이를 의미한다.

따라서 해당 값을 더해 2의 길이를 가질 것이고 이 또한 메모리제이션 테이블에 저장한다.

 

 

 

---

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2	1

 

0	1	2
0	5	20

 

5에 대해서 살펴보자. 메모리제이션 테이블을 보니 5보다 작은 값이 없으므로, 길이는 1이다.

기존에 길이 1을 만족시키던 최소값이 10이었으므로 해당 값을 더 작은 최소값인 5로 갱신시켜 주어야 한다.

 

 

 

---

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2	1	3

 

0	1	2	3
0	5	20	30

 

30에 대해서 살펴보자. 메모리제이션 테이블을 보니 30보다 작은 값에 해당하는 길이가 2였으므로 길이는 3이 된다.

마찬가지로 메모리제이션 테이블에도 넣어주자.

 

 

---

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2	1	3	2

 

0	1	2	3
0	5	10	30

 

다음 10에 대해서 살펴보자. 메모리제이션 테이블을 보니 10보다 작은 값에 해당하는 값인 5가 존재하고 길이가 1였이므로 해당 길이는 2가 된다.

만약 길이 1에 해당하는 메모리제이션 테이블이 최소값 5가 아닌 10이었다면 길이가 1이 되었을 것이다. 따라서 앞에서 왜 최소값으로 갱신이 필요한지를 알려준다.

메모리제이션 테이블에 길이 2에 해당하는 값이 현재 값보다 크므로 최소값인 10으로 갱신해주자.

 

 

 

---

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2	1	3	2	4

 

0	1	2	3	4
0	5	10	30	50

 

마지막으로 50에 해당하는 값보다 작은 것 중 최장길이는 3이므로, 해당 LIS는 4가 된다.

이를 메모리제이션 테이블에 저장해준다.

 

 

 

---

해답 도출

 

0	1	2	3	4
0	5	10	30	50

 

메모리제이션 테이블에는 지금까지 구해왔던 수열의 길이들이 저장되어 있다. 이들 중 최대값인 4가 정답이 된다.

또한 해당 테이블은 항상 오름차순으로 정렬된다. 따라서 탐색 알고리즘으로 이진 탐색을 사용하면 좋겠다는 생각을 할 수 있다.

 

0	1	2	3	4	5	6
0	10	20	5	30	10	50
0	1	2	1	3	2	4

 

그리고 사실 해당 테이블에서, LIS를 저장하고 있던 셀들도 해당 로직으로 변경하면, 더 이상 사용되지 않는다.

LIS의 최대 길이는 위의 테이블을 통해 알 수 있고, 해당 테이블을 갱신하는 과정에서는 Value만 필요할 뿐, 이전의 LIS는 필요하지 않기 때문이다.

 

 

---

코드 작성 : LIS 개선

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


public class Main {
    static Integer[] numbers;
    static Integer[] dp;



    // 해당 원소가 오른쪽에 삽입되기 전 가질 수 있는 이전 수열의 LIS 최대 길이를 반환
    static int binarySearch(int value, int left, int right){
        if(left == right){
            return left - 1;    //탐색 성공 위치의 이전 값이 이전 최대 LIS
        }
        else{
            int mid = (left + right) / 2;
            if(dp[mid] == value){
                return mid - 1;  //탐색 성공 위치의 이전 값이 이전 최대 LIS
            }
            else if(dp[mid] > value){
                return binarySearch(value, left, mid);
            }
            else{
                return binarySearch(value, mid + 1, right);
            }
        }
    }

    // 해당 원소가 오른쪽에 삽입되기 전 가질 수 있는 기존 LIS의 길이를 반환. 탐색 범위는 1부터 지금까지 LIS 중 최대 길이까지.
    static int binarySearch(int value, int size){
        return binarySearch(value, 1, size + 1);
    }



    static int lis(int n){
        int max = 0;
        for(int i = 1; i <= n; i++){
            int num = numbers[i];
            int d = binarySearch(num, max); // 이진 탐색을 통해서 dp 배열에서 해당 값 이전에 올 수 있는 LIS의 길이 탐색
            int index = d + 1;  //현재 LIS의 길이
            dp[index] = Math.min(dp[index], num);   // dp 최소값 갱신
            max = Math.max(max, index); // 결과로 반환할 LIS 최대값 갱신
        }
        return max;

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        numbers = new Integer[n + 1];
        dp = new Integer[n + 1];


        numbers[0] = 0;
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(lis(n));

    }
}

 

각각의 수열의 길이에 해당하는 최소값을 dp 배열에 저장해두고, 이를 기반으로 최장 길이를 찾는 로직으로 변경하였다.

위에서 설명한 방식대로 수열의 맨 처음부터 끝까지 아래의 방법을 사용한다.

1. 해당 값 이전에 올 수 있는 수열(LIS)의 최대 길이를 dp에서 이진 탐색을 통해 찾는다.

• 최대 길이는 dp 배열의 index이다.
• 이를 위해서 이진 탐색의 Upper Bound 방식으로 이전에 오는것이 불가능한 첫번째 인덱스를 찾는다. 해당 인덱스에서 1을 뺄셈한 값이, 이전에 올 수 있는 수열의 최대 길이이다. 

2. dp[i]를 기존 메모리제이션 값과, 현재 값을 비교하여 최소값으로 갱신한다.

3. 동시에 dp에 들어있는 수열의 길이의 최대값을 계산하여, 이를 이진 탐색 범위 및 최종 결과 LIS로 사용한다.

<함께 보기> 이진 탐색 (Lower Bound와 Upper Bound)

https://sjh9708.tistory.com/218

[알고리즘/JAVA] 이진 탐색 : 개념 (수 찾기, 랜선 자르기 (Upper/Lower Bound))

 

---

결과

 

 

결과를 보면 수행 시간이 줄어든 것을 확인할 수 있다. 해당 방식을 사용할 시 시간 복잡도를 O(N^2)에서 O(NlogN)으로 개선할 수 있다.