최장 증가 부분 수열(LIS)

최장 증가 부분 수열이란?

어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로, 순서를 유지한 채 몇 개의 숫자들을 뽑아서 부분 수열을 만들 수 있다.
이렇게 만들 수 있는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다.
예를 들어, [6, 2, 1, 4, 3, 5]라는 수열이 있다면마지막 원소 5를 붙일 거라면, 5보다 앞에 있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙이는 것이 좋다.
[1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이다. (여러 개 일 수 있다. )

DP를 활용하여 O(N²)으로 구해보기

배열의 숫자를 하나씩 살펴보면서 LIS의 길이를 구하는 방법

DP[i] : 마지막으로 뽑은 수가 A[i]일 때의 가장 긴 부분 수열의 길이
지금까지 만들어 놓은 증가 수열에 A[i]를 붙일 수 있으려면
1. 만들어 놓은 증가 수열이 A[i]보다 앞에 있어야 한다. ⇒ j<i
2. 마지막 수가 A[i]보다 작아야 한다. ⇒ A[j]<A[i]

모든 dp배열의 값은 최소 1이므로 이미 1로 초기화 됨

        int max = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j]+1);
                // 이전 원소들 중 가장 큰 dp값 + 1
            }
            max = Math.max(max, dp[i]);  //LIS 길이 구하기
        }
        System.out.print(max);

N개의 수들에 대해서 현재 위치 이전의 모든 수를 다 훑어봐야 하므로 O(N²)의 시간복잡도를 가지게 된다.

Binary Search를 이용하여 O(NlogN)으로 구해보기

굳이 N개의 수들에 대해서 현재 위치 이전의 모든 수를 반복하며 훑어봐야할까?
라는 의문을 가지게 된다.

⇒ dp[j] =k를 만족하는 j중 A[j]의 값이 가장 작은 값만 저장해 높으면 전체를 다 확인할 필요가 없다.

⇒ 이분 탐색을 이용하면 모든 수열의 값을 일일히 비교하지 않고 LIS의 길이를 구할 수 있다.

A[i] : i번째 수열의 값을 저장한 배열
dp[i] : 증가 부분 수열의 길이를 저장해 놓는 배열
list[k] : k길이의 증가 수열에 대하여 가장 작은 값을 list[k]에 저장,
각 위치에서의 list[k]를 갱신하기 위해서 이분 탐색을 수행한다. 초기에 list[0]의 가장 작은 값을 넣어둔다.

i=0일 때,

A[0]이 list에 어디에 들어갈 수 있는지 찾는다. 마지막 값보다 크므로 바로 뒤에 새롭게 넣는다.

i=1일 때,

A[1]=11은 list의 가장 마지막 값이 2보다 크다.

이 말은 현재 A[1] 앞의 수들로 만든 가장 긴 증가 부분 수열 중 마지막 값이 2인 증가 부분 수열이 있다는 말입니다.

list의 마지막에 11를 추가해주고, dp[1]=2을 넣어준다

i=2일 때,

가장 마지막 값인 11보다 작으므로, 이분 탐색을 통해 들어갈 자리를 찾는다.

4는 2와 11 사이의 값이므로, 마지막 값을 2로 하는 부분 증가 수열의 뒤에 추가할 수 있다.

list[2]의 값을 4로 갱신해주고, dp[2]=2를 넣어준다.

i=3일 때,

A[3]인 55가 list의 마지막 값인 4보다 크다. list의 55를 추가해주고, dp[3]=3을 넣어준다

i=4일 때,

A[4]=7은 마지막 list의 값인 55보다 작고, 7은 4와 55 사이의 수 이다.

따라서 55를 이제 7로 갱신하고, dp[4]=3을 넣어준다.

i=5일 때,

A[5]=9는 list의 마지막 값인 7보다 크다. list의 9를 추가해주고, dp[5]=4을 넣어준다

i=6일 때,

A[6]=13가 list의 마지막 값인 9보다 크다. list의 13를 추가해주고, dp[6]=5을 넣어준다

i=7일 때,

가장 마지막 값인 13보다 작으므로, 이분 탐색을 통해 들어갈 자리를 찾는다.

3는 2와 4 사이의 값이므로, 마지막 값을 2로 하는 부분 증가 수열의 뒤에 추가할 수 있다.

list[2]의 값을 3로 갱신해주고, dp[7]=2를 넣어준다.

list 배열을 항상 오름차순으로 정렬되어 있기 때문에 A[i]의 값이 list의 어느 위치에 들어갈 수 있는지 이분 탐색을 활용하여 찾을 수 있다.
list의 마지막 index가 LIS의 길이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class LIS{

    static int N;
    static int[] A;
    static int[] dp;
    static ArrayList<Integer> listForSize;
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A= new int[N+1];
        dp = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        listForSize = new ArrayList<>();
        listForSize.add(Integer.MIN_VALUE);

        for(int i=0;i<N;i++){

            if(listForSize.get(listForSize.size()-1) < A[i]){ //가장 마지막 수열보다 현재 수열이 클 때
                listForSize.add(A[i]);
                dp[i] = listForSize.size()-1;
            }else{
                //listForSize에서 A[i]보다 처음으로 크거나 같아지는 원소의 index찾기 : Lower bound
                int index = binarySearch(1,listForSize.size()-1,A[i]);
                listForSize.set(index,A[i]);
                dp[i]=index;
            }
        }
        int LISLength = listForSize.size() - 1;
        System.out.println(LISLength); //LIS길이 출력
    }

    //현재 수열이 들어갈 수 있는 위치를 빠르게 찾아주기 위한 바이너리 서치 구현하기
    private static int binarySearch(int left, int right, int target) {
        while(left<right){
            int mid = (left+right)/2;
            if(target> listForSize.get(mid))
                left = mid+1;
            else right=mid;
        }
        return left;
    }
}

[최장 부분 증가 수열 출력]

뒤에서 부터 탐색해, LIS의 길이를 기준으로 값을 감소시키며, 동일한 값을 가지는 dp[i]를 찾고 A[i]를 출력한다.

⇒ [2, 4, 7, 8, 13]이 정답!

//뒤에서부터 탐색하며, LIS출력
        Stack<Integer> stack = new Stack<>();
        int index =LISLength;
        for(int i=N-1;i>=0;i--){
            if(dp[i] == index) {
                stack.push(A[i]);
                index--;
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop()+" ");
        }
        System.out.println(sb);

시간복잡도는 원 배열을 순회하고 O(N) 각 순회에서 이진 탐색하는O(logN) 과정이 묶여 있다. 따라서 시간복잡도는 O(NlogN) 이 될 것 같은데 그거보다 사실 더 좋다.
각 이진 탐색 과정에 두번째 인자를 lis의 길이 변수로 줬는데, 이 변수는 결국 lis의 길이의 수렴한다. lis의 길이를 K라고 할 때, K<=N는 언제나 성립하기에 따라서 O(NlogK) ≤ O(NlogN)도 성립하고 최종적인 시간복잡도는 O(NlogK)가 된다. 이는 탐색의 두 번째 값을 배열의 크기로 고정하지 않고 유동적인 변수를 썼기에 가능한 성과기도 하다.

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

Knapsack 알고리즘

어떤 배낭이 있고 그 배낭 안에 넣을 수 있는 최대 무게가 K가 있다. 배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치 V를 가지고 있고 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다.
Fractional Knapsack : 물건을 쪼갤 수 있어 무게나 가치가 소수점 단위로 나뉘는 유형
- 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로 그리디 알고리즘으로 해결할 수 있다.
0 -1 Knapsack : 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수 형태를 가지는 유형
- 동적계획법(DP, Dynamic Programming)을 활용해 해결할 수 있다.

0 -1 Knapsack: Dynamic Programming으로 해결하기

subProblem 정의하기

무게 7의 가방을 최대 가치로 가득 채우려면 무게 6일때 최대 가치로 가득 채웠을 때의 조합에 하나가 더 들어갈 수 있는지 확인해보면 되지 않을까?
⇒ 잘못된 생각 : 하나의 물건을 빼고 다른 하나를 넣는 것으로 최대 가치를 만들 수 있다.

배낭에 물 건을 넣을 때 선택할 수 있는 경우의 수는
- 물건을 넣는 경우
- 물건을 넣지 않는 경우

w: 최대 무게

i: 현재 넣을 물건의 번호

wk: i번째 물건에 대한 무게

DP[i][w]: i개의 물건이 있고 배낭의 무게 한도가 w일 때 최적의 이익

넣으려고 하는 물건의 무게가 배낭의 제한 무게를 초과한다면, 선택지는 물건을 넣지 않는 경우밖에 없다.
💡 DP[i][w] = DP[i-1][w], if wi > w

만약, 배낭의 물건을 넣을 수 있는 무게가 조금이라도 남았다면
- 물건을 넣지 않는다.
- 새로운 물건을 넣기 위해 물건을 넣을 공간을 만들어서 물건을 넣는다.
  → 현재 물건을 넣기 위해 물건을 뺏을 때의 가치에 현재 물건의 가치를 더해준다.
- 최대 가치를 찾는 것 이기 때문에 두 경우 중 더 큰 값을 선택하면 된다.
- 💡 DP[i][w] = max(DP[i-1][w], DP[i-1][w-wi] + vk) else

⇒ 2차원 배열을 채워나가면서, 필요한 경우 "앞에서 계산했던 다른 칸의 값을 이용해서" 다음 칸의 값을 계산한다

예제 풀어보기

배낭의 용량 C = 7kg일 때, 배낭에 담을 수 있는 물건의 최대 가치는 얼마인지 구해봅시다!

DP[i][w]: i개의 물건이 있고 배낭의 무게 한도가 w일 때 최적의 이익

i: 물건 i까지 넣을 수 있을 때, w는 가방의 최대 무게를 의미

일단 i가 0인 경우는 넣을 물건이 없는 것이므로 다 0이고, w가 0인 경우는 배낭에 넣을 수 있는 무게가 없다는 것이므로 다 0이다. 첫번째 행이랑 첫번째 열은 다 0으로 채워 넣고 시작한다.

i=1일 때, 무게 6, 가치 13

[1, 1] ~[1,5] 인 경우에는 배낭에 물건을 넣을 수 없다.

[1.6]인 경우에는 이제 1번 물건을 넣을 수 있으므로 DP[1, 6] = 13이 된다

(1번 물건의 가치 + DP[0, 0]) 의 값과 DP[0, 6] 의 값을 비교해서 더 큰 쪽을 가져가게 된다.

i=2일 때, 무게 4, 가치 8

[2,1] ~ [2,3]인 경우에는, 2번 물건을 넣을 수 없다. 바로 윗 칸의 값을 가져온다.

[2,4]이 되면 2번 물건을 넣을 수 있게 있다.
1번 물건을 넣었을 때 (바로 윗칸) 과 2번 물건을 넣을 만큼의 공간을 확보하고 2번 물건을 넣었을 때 (즉, 2번 물건의 가치 + DP[1, 0]) 를 비교해서 더 가치가 높은 쪽을 선택한다.

i=3일 때, 무게 3, 가치 6

[3,1]~[3,2]: 물건을 넣을 수 없다. 바로 윗 칸의 값을 가져온다.

[3,3] ~ [3,7]까지 최적 값을 가져온다

[i, w] 가 (3, 7) 인 경우에는 2번과 3번 물건을 둘 다 넣을 수 있다.
이미 8이 들어있는 (2, 4) 에서 최적 값을 가져온다는 것이 2번 물건을 빼지 않고도 3번 물건을 넣을 수 있음을 의미한다. 즉 2번 물건을 넣었던 칸의 최적값 (8) + 3번 물건의 가치 6의 합이 들어간다.

i=4일 때, 무게 5, 가치 12

나머지 칸들도 계산해보면 마지막 칸에는 결국 14가 들어가고, 이 마지막 칸의 값이 최종적인 답 (최적의 총 가치) 이 된다.

코드 완성하기

private static int getToalValue() {

    for(int i=1;i<=N;i++){
        for(int w=1;w<=K;w++){
            if(W[i] <= w) //i번째 물건을 들어갈 수 있다
                                dp[i][w] = Math.max(V[i] +dp[i-1][w-W[i]],dp[i-1][w]);
            else
                                dp[i][w] =dp[i-1][w];
                    }
        }
    return dp[N][K];
}

전체 코드

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

public class Knapsack {
    static int N,K;
    static int[] W,V, dp[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N= Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N+1][K+1];
        W= new int[N+1];
        V= new int[N+1];

        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            W[i]=Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }
        int result = getToalValue();
        System.out.println(result);

    }

    private static int getToalValue() {

        for(int i=1;i<=N;i++){
            for(int w=1;w<=K;w++){
                if(W[i] <= w){ //i번째 물건을 들어갈 수 있다
                    dp[i][w] = Math.max(V[i] + dp[i-1][w-W[i]], dp[i-1][w]);}
                else
                    dp[i][w] = dp[i-1][w];
            }
        }
        return dp[N][K];
    }
}

public class Knapsack_1 {
    static int N,K;
    static int[] W,V, dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N= Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[K+1];
        W= new int[N+1];
        V= new int[N+1];

        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            W[i]=Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }
        int result = getToalValue();
        System.out.println(result);

    }

    private static int getToalValue() {

        for(int i=1;i<=N;i++){
            for(int w=K;w>0;w--){
                if(W[i] <= w){ //i번째 물건을 들어갈 수 있다
                    dp[w] = Math.max(V[i] + dp[w-W[i]], dp[w]);}
            }
        }
        return dp[K];
    }
}

시간복잡도

부분문제의 개수는 2차원 배열의 크기인 N* K이므로, 배낭 문제의 시간복잡도는 O(N*K) 이다.

여기서 배낭의 용량 K가 물건의 개수 n에 비해 너무 커지면, 알고리즘의 수행 시간이 너무 길어져 현실적으로 해를 찾을 수 없다. 따라서 배낭 문제는 제한적인 입력 크기에 대해서만 효용성을 갖는다.

12865번: 평범한 배낭

2568번: 전깃줄 - 2

'JAVA > Algo 개념' 카테고리의 다른 글

KMP -JAVA (0)	2023.08.05
양방향 연결리스트 구현하기 (0)	2023.08.05
슬라이딩 윈도우와 투 포인터 (0)	2023.07.30
TreeMap - Red-Black Tree (0)	2023.07.26
SegmentTree 개념 (0)	2023.07.13

DP - LIS(최장 증가 수열) 및 0-1 Knapsack 개념 (JAVA)