LIS 최장증가수열 알고리즘 :: 마이구미

이번 글의 주제는 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을 기준으로 차례대로 들려보자.

10, 20 ,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