LIS - 최장 증가 부분 수열 알아보기

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다

• 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이다.
• 이는{ 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 때문!!

 

문제

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

풀이 방법

풀이 요점 : 0 ~ i-1 까지 검사하면서 각 항마다 최대 증가 수열의 최대값을 찾고, 거기에 +1 한다

코드 확인

package algorithm;

// 최대부분증가수열
/*
 i 번째 숫자를 마지막항으로 하는 최대 증가 수열
 주어지는 배열에서 i 번째 항(index) 를 기준으로 만들 수 있는 최대의 증가 수열
 { 5 3 7 8 6 2 9 4 } 라는 배열이 있을 때
 arr[3] = 8 을 기준으로 올 수 있는 최대의 증가수열의 갯수를 구한다
 {3,7,8}
 {7,8}
 {5,7,8}
 {5,3,7,8} 의 경우에는 5->3 으로 증가하는 것이 아닌 감소하기 때문에 허용X

 풀이 요점 : 0 ~ i-1 까지 검사하면서 각 항마다 최대 증가 수열의 최대값을 찾고, 거기에 +1 한다
* */

public class Dp_2_LIS {
    // 각 인덱스(항) 의 최대부분증가 수열의 길이를 저장
    static int[] dy;
    public static void main(String[] args){
        int[] arr = {5, 3, 7, 8, 6, 2, 9, 4};
        System.out.println(sol(arr));
    }

    static int sol(int[] arr){
        int answer = 0;

        dy = new int[arr.length];
        // 0번째 인덱스의 최대 부분증가수열은 하나 밖에 없음으로 1
        dy[0] = 1;

        for(int i=1; i<arr.length; i++){
            int max = 0;

            // i보다 작은 index 를 기준으로 가장 큰 최대 부분 증가 수열을 찾는다
            for(int j=i-1; j>=0; j--){
                // dy[i] 번째 값의 최대 증가 수열의 길이를 찾기 위해서는
                // j 가 i 보다 작으면서, dy[j] 까지의 값들 중 최대값이 되는 값을 찾아야한다.
                // 이는 j 가 i 보다 작으면 당연히 그 다음에 i 가 올 수 있고, 결국
                // dy[j] 의 최장 증가 수열에서 앞에 i 를 하나 붙여주면 i 의 최장 증가 수열을 구할 수 있기 때문이다.

                // 9 의 증가 부분 수열은
                // {3,7,8}, {5,7,8} {7,8} 등등 있다. 이때 최장 증가 부분 수열은 결국 {3,7,8,9} 아니면{5,7,8,9} 가 된다
                // 즉 i-1 => dy[j] 의 값들 중 가장 큰 값 +1 이 되는 것이다

                if(arr[j]<arr[i] && dy[j]>max){
                    // dy[j] 중에 max 보다 큰 수가 있다면
                    // 0 ~ j(i-1) 중에서 가장큰 부분증가수열이 됨
                    max = dy[j];
                }

                // i 번째 항의 최대 부분 수열의 값은 max+1
                dy[i] = max+1;
            }

            // 각 항의 최대 부분증가수열의 값이 들어있는 dy 중에서
            // 가장 큰 값을 찾으면 그게 바로 정답!!
            answer = Math.max(answer, dy[i]);
        }

        return answer;
    }
}

 

발전 문제 : 가장 높이 벽돌 쌓기

 첫째줄에 벽돌의 수가 주어지고
 둘째줄부터 각 줄에 한 개의 벽돌에 관한 정보인 벽돌의 밑면의 넓이, 벽돌의 높이, 무게가 차례대로 주어진다

  이때 가장 높이 쌓을 수 잇는 벽돌의 높이는?

풀이 방법

위에서 사용했던 방법 그대로! 사용한다.

특히 LIS 의 풀이 요점은 dy 배열에 0 ~ i-1 까지 검사하면서 0~i-1 까지의 각 항의 최대 증가 수열을 찾아서 저장한다.

이때 dy[i] 의 값은 dy[0] ~ dy[i-1] 까지의 값들 중 최대값 +1 이 된다는 점을 명심히자

package algorithm;

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

// 가장 높은 탑 쌓기 LIS
/*
 첫째줄에 벽돌의 수가 주어지고
 둘째줄부터 각 줄에 한 개의 벽돌에 관한 정보인 벽돌의 밑면의 넓이, 벽돌의 높이, 무게가 차례대로 주어진다

  이때 가장 높이 쌓을 수 잇는 벽돌의 높이는?
*
* */
public class Dp_2_2_LIS {
    // i 번째 벽돌을 가장 위에 놓았을 때 벽돌의 최대 높이
    static int[] dy;

    // 벽돌에 대한 정보를 저장하기 위한 list
    static ArrayList<Stone> list = new ArrayList<Stone>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dy = new int[n];

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            list.add(new Stone(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // 벽돌을 넓이 기준 내림차순 정렬
        // 이 정렬을 통해 넓이는 이미 계산되었고, 높이만 계산하면 됨
        Collections.sort(list , (o1, o2)->{
            return o2.s - o1.s;
        });

        list.forEach((o)->{
            System.out.println(o.s+" "+o.w);
        });

        System.out.println(sol());
    }

    static int sol(){
        // dy 의 가장 첫번째에는 list 의 0번째 벽돌이 위치하게 됨
        dy[0] = list.get(0).h;

        // answer 은 dy[0] 으로 초기화해야하는데
        // 이는 맨 처음의 높이가 가장 큰 높이가 될 수 있기 때문임
        int answer = dy[0];

        // list 가 돌기 시작
        // 이때 list i 번째 값이 탑의 가장 위에 위치하게 됨
        // 즉 밑의 작업은 i 번째 벽돌의 밑에 올 수 있는 벽돌을 찾고,
        // 동시에 최대 높이로 만들 수 있는 값을 찾는 것
        for(int i=1; i<list.size(); i++){
            int maxH = 0;

            for(int j=i-1; j>=0; j--){

                // i 번째의 벽돌이 가장 위에 잇고, 아래에는 i 번째 벽돌보다 무거운 벽돌이 와야한다
                // dy 에는 i 번째 벽돌을 가장위에 올려두었을 때 구할수 잇는 최대 높이가 저장됨

                // 이때 i 번째 벽돌 아래에 j 번째 벽돌이 올 수 있다면 결국 j 번째 벽돌까지의 최대 높이가
                // i 번째 벽돌을 맨 위에 두는 최대값이 된다.
               if(list.get(j).w > list.get(i).w && dy[j]>maxH){
                    maxH = dy[j];
                }
            }

            // 최종적으로 i 번째 벽돌의 높이는 i-1 에서 계산된 최대 높이값 + i 번째 벽돌의 높이
            dy[i] = maxH + list.get(i).h;

            // dy[i] 에서도 최대값을 찾는다
            answer = Math.max(answer, dy[i]);
        }

        return answer;
    }
}

class Stone{
    int s;
    int h, w;

    Stone(int s, int h, int w) {
        this.s = s;
        this.h = h;
        this.w = w;
    }
}