• LIS 최장증가수열 알고리즘 :: 마이구미
    알고리즘 2016. 12. 10. 11:55
    반응형

    이번 글의 주제는 LIS 알고리즘이다.

    LIS는 Longest Increasing Subsequence 로써 최장증가부분수열이라는 의미이다.

    시간복잡도 O(n^2)을 다룰 것이고, O(nlogn)의 경우는 링크를 보자. (관련 글)


    백준 알고리즘 11053번 11055번을 가지고 진행할 것이다.

    최장증가수열은 무엇인지 백준 알고리즘 사이트 문제만 읽어도 알 수 있다.


    수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

    예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.


    위와 같은 경우가 증가 부분 수열이다.

    본인은 이번 글에서 이 문제를 가장 기본적인 풀이 방식으로 다룰 것이다.

    본인은 LIS 알고리즘을 DP, 즉 동적계획법으로 접근하는 방식을 보여줄 것이다.

    동적계획법이라 하면 머리 아플 것이다...

    하지만 동적계획법을 잘 이해하지 못하고, 그 문제라면 건너뛰는 사람도 많다.

    이번 문제는 동적계획법의 기초와 접근 방식을 알 수 있음으로 읽어보길 바란다.


    가장 긴 증가 부분 수열에 관한 LIS 알고리즘을 구현한 소스를 보자.

    이중 반복문이 끝이다. 

    이것만 이해하면 되니까 두려워말자.


    int[] array = new int[N]; // 인덱스마다 각 입력값

    int[] dp = new int[N]; // 인덱스마다 각 증가 수열의 길이

    int max = 0;

    dp[0] = 1;

    for(int i=1;i<N;i++) { dp[i] = 1; // i 를 기준으로 인덱스 0 에서부터 i-1까지 체크한다 // 길이를 기준 for(int j=0;j<i;j++) { if (array[i] > array[j] && dp[j] + 1 > dp[i]) { // 증가 수열 dp[i] = dp[j] + 1; } } if (max < dp[i]) { max = dp[i]; } }


    가장 중요한 건 dp 배열이다.

    dp 배열은 증가 수열의 길이를 넣을 것이다.

    일단 이중 반복문을 보자.


    for(int i=1;i<N;i++) {     ........

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

    ........

    }

    }


    기본적으로 i는 N까지 돌고 두번째 반복문은 0부터 i 전까지 돌게 된다.

    배열에 10,20,10,30,20,50 값이 있다고 가정하자.

    i = 1 -> 10 .. (20 기준 )

    i = 2 -> 10, 20 .. (10 기준)

    i = 3 -> 10, 20 ,10 .. (30 기준)

    i = 4 -> 10, 20, 10, 30 .. (20 기준)

    i = 5 -> 10, 20, 10, 30 ,20 .. (50 기준) 

    이런 식으로 하나를 기준으로 잡아 루프를 돌게 된다.

    그렇다면 다시 전체적인 이중 반복문을 보자.


    for(int i=1;i<N;i++) {    dp[i] = 1;

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

    if (array[i] > array[j] && dp[i] < dp[j] + 1) {

    dp[i] = dp[j] + 1;

    }

    }

    }


    하나를 기준으로 잡아 그 전에 값들을 비교해서 길이를 정하는 방식이다.

    기본적으로 어찌되든 길이는 1로 시작한다.

    당연히 array[i] 가 array[j]보다 커야하고, 길이를 증가할 수 있는지에 대한 조건을 주게 된다.


    길이를 증가할 수 있는지에 대한 조건에 대해 의문이 들 수 있으니 예를 들어보자.

    위에서 가정한 예제 중에서 i = 3 -> 10, 20 ,10 .. (30 기준)

    30을 기준으로 dp[3]의 값은 3이 나와야한다.

    하지만 길이에 대한 조건을 뺀 후 돌려보면 알 수 있다.


    if (array[i] > array[j] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; }


    30을 기준으로 차례대로 들려보자.

    1020 ,10

    10 => dp[3] = 2

    20 => dp[3] = 3

    10 => dp[3] = 2

    30은 차례대로 들리는 10, 20, 10보다 크기 때문에 조건에 성립하게 된다.

    그 결과 위와 같이 dp의 값이 작은 수로 갱신되어버리는 버그가 발생한다.

    그렇기 때문에 갱신돼버리는 경우를 배제시켜야하기 때문에 조건을 추가한다.


    이렇게 루프를 돌 때마다 dp 배열에는 해당 기준에 대한 길이가 저장되게 된다.

    그렇기 때문에 i가 증가할 때마다 dp 배열에 있는 길이를 사용하여 dp 배열은 계속해서 갱신되어 원하는 값을 얻게 된다.

    이렇게 dp 배열 중 가장 큰 값이 가장 긴 증가 수열의 길이가 되는 것이다.


    이해와 완벽히 습득하기 위해 살짝 바꿔보자.

    가장 합이 큰 증가 수열을 구해보자.


    수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

    예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.


    위와 접근 방식은 동일하다.

    그렇다면 dp 배열을 어떻게 접근하여 값을 관리할 것인지 고민을 해야한다.

    (많은 고민을 해보고 읽기 바란다.)

    본인은 이렇게 생각했다.

    결국 길이가 합으로 바뀌는 것이고, 다른 건 달라진 게 없다.

    dp[i] 가 갱신될 값이니 dp[i] 보다 비교 대상이 크다면 갱신 시켜버리면 된다.

    아래와 같이 생각했다.


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

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

    if (array[i] > array[j] && dp[i] < dp[j] + array[i]) {

    dp[i] = dp[j] + array[i];


    }

    }

    }


    조건에 맞는다면 기준을 잡은 값 + dp 배열의 값을 더해주었다.

    길이를 구할 때는 dp 배열의 값을 1로 시작하였다.

    합일 경우는 미리 array 배열과 같이 값을 넣어주게 되면 원하는 결과값을 얻게 된다.


    아래 세 문제의 링크를 둘 것이다.

    이번 글만 잘 이해했다면 충분히 쉽게 풀 것이다.

    소스는 Github을 통해 확인하면 된다.


    LIS 관련 문제 소스 Github URL

    https://github.com/hotehrud/acmicpc/tree/master/algorithm/lis


    백준 11055번 가장 큰 증가 부분 수열

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


    백준 1965번 상자 넣기

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


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

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


    반응형

    댓글

Designed by Tistory.