[Algorithm] DP - LIS

LIS(Longest Increasing Subsequence)

최장 증가 부분 수열로 부분 수열의 원소가 오름차순을 유지하면서 길이가 가장 큰 부분 수열을 말한다.

이를  이해 하기 위해서는 부분 수열에 대해 먼저 알 필요가 있다.

 

 

 

 

 

부분수열

주어진 수열 중 일부를 뽑아서 새로 만든 수열을 뜻하고, 이때 각각의 원소는 전후 관계를 유지해야 된다.

예를 들어 {1, 7, 5, 10, 8} 이라는 수열이 있다고 하자.

여기서 원소 1, 5, 8을 뽑았을 때 {1, 5, 8} 이렇게 뽑을 경우 원래의 순서를 유지한 채 뽑았기에 부분수열이고

{1, 8, 5} 이렇게 뽑았을 경우 원래 수열은 5다음 8이 와야하는데 현재의 수열은 8다음 5가 나왔기 때문에

원래의 순서를 유지하지 않았으므로 부분수열이 아니다.

여기서 부분수열의 길이는 원소의 개수로 3이다.

 

 

 

 

최장증가부분수열

이러한 부분 수열 중에서 원소들이 오름차순으로 정렬되어 있고, 가장 긴 수열을 LIS라고 부른다.

{1, 7, 5, 10 8} 이라는 수열이 있다. 여기서 몇개의 부분 수열을 만들어 보겠다.

{1, 7, 5} -> 원래의 순서를 지킨 부분 수열이지만 오름차순 정렬이 되어 있지 않아서 LIS가 아니다.

{5, 8} -> 원래의 순서를 지키고, 오름차순 정렬이 되어 있기 때문에 LIS의 후보가 된다.

{7, 5, 1, 10} -> 원래의 순서를 지키지 않아서 일반 수열이다.

{1, 5, 8} -> 원래의 순서르 지키고, 오름차순 정렬이 되어 있으므로 LIS의 후보이다.

 

 

그럼 LIS 후보 들 중에 가장 긴 수열을 선택하면 그게 LIS가 된다.

{5, 8}의 길이는 2고, {1, 5, 8}의 길이는 3이므로 해당 수열의 LIS는 {1, 5, 8}으로 3이 된다.

 

 

 

 

 

 

 

LIS 알고리즘 DP

LIS 문제는 동적 프로그래밍(DP)나 이진탐색을 통해서 해결할 수 있다.

DP의 경우 시간 복잡도가 O(N^2)이고, 이진탐색은 O(N log N)으로

N의 개수가 1000 미만일 때는 DP가 적합하고 N의 개수가 크면 이진탐색을 사용하는게 적합하다.

다만, 본 글에서는 DP를 이용한 탐색 방법을 제시한다.

 

 

 

 

기존의 배열 arr[]에서 n개의 증가하는 부분수열의 길이가 나오고, 이 부분 수열 중에 가장 긴 부분수열이 LIS가 된다.

이때 LIS를 구성하는 원소의 개수를 찾기 위해서 dp[]라는 배열이 사용된다.

기존 배열 arr = {10, 20, 10, 30, 20 ,50}이 주어졌다고 하자.

 

 

 

 

이때 만들 수 있는 증가하는 부분 수열은

개수가 1개인 {10], {20}, {10}, {30}, {20}, {50}

개수가 2개인 {10, 20}, {10, 30}, {20, 30}, {30, 50}, {20, 50}

개수가 3, n,... 등등 다양하게 많다. 우리는 최종적으로 n개일 때의 부분수열인 LIS를 구하는게 목표고

이를 구하기 위해서는 dp[]배열이 사용된다.

 

 

dp[i]는 arr[i]원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이라고 칭한다.

dp[4]의 경우 arr[4]인 30원소를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이로

{30}, {10, 20, 30} 2개의 증가하는 부분수열이 나오고 이 중 {10, 20, 30}이 가장 길어서 3이 저장된다.

모든 dp값에는 값이 1로 초기화가 되는데 이는 arr의 원소는 그 자체로 길이가 1인 LIS가 되기 때문이다.

 

 

 

LIS의 풀이방법은 간단하다.

1. 배열에서 자기보다 앞에 있는 원소들과 비교하면서 오름차순인지 확인하다.

2. 1조건 조건이 참이면 dp의 값을 업데이트 한다.

3. 배열의 모든 원소를 돌 때 까지 반복한다.

 

 

 

 

핵심코드는 아래와 같다.

바깥쪽 반복문을 통해서 arr 배열의 모든 원소를 순회하면서 각 원소로 끝나는 증가하는 가장 긴 길이를 찾는다.

안쪽 반복문을 통하여 바깥쪽 arr의 원소 i보다 앞에 있는 즉 arr[0~(i-1)]를 순회하면서 증가하는 수열인지를 확인한다.

만약 arr[i] > arr[j]일 경우 arr[i]를 arr[j] 마지막으로 하는 증가 부분 수열의 끝에 붙일 수 있다.

즉 {10, 20, 30}부분 수열이 있고 30과 40을 비교했을때, {10, 20, 30, 40}으로 30뒤에 붙일 수 있다는 의미이다.

 

 

부분수열의 원소가 증가 했으므로(길이가 3->4로 늘어남)  dp가 업데이트 되어야 한다.

이때 Math.max(dp[i], dp[j]+1)로 업데이트를 하는데, 현재 40을 끝으로 가지면서 증가하는 부분 수열 원소의 수와

30을 마지막으로 가지면서 증가하는 부분 수열 원소의 수 + 1(위에서 10, 20, 30 -> 10, 20, 30, 40으로 원소의 개수 증가)를 

비교하여 arr[i]=40, dp[i] ->40을 마지막으로 가지는 증가하는 가장 긴 부분수열의 수로 업데이트 한다.

 

 

이 과정은 모든 j에 대해 반복하면, dp[i]는 arr[i]보다 앞에 있는 모든 arr[j]중에 arr[i] > arr[j] 조건을 만족하는 경우를 확인하고

그리고 그중에서 증가하는 가장 긴 부분수열을 만들어주는 j를 선택하여 깊이를 갱신하게 된다.

        for(int i=0; i<N; i++){
            for(int j=0; j<i; j++){
                if(arr[i] > arr[j]){ //1 번째 조건 오름차순이어야함
                   dp[i] = Math.max(dp[i], dp[j]+1); // dp 업데이트
                }

            }

 

 

 

 

 

 

 

 

 

초기상태는 다음과 같다.

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 1, 1, 1, 1]

 

 

 

 

 

 

 

 

 

i=1일때

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 1, 1, 1, 1]

j=0일때 arr[1]=20, arr[0]=10, dp[0]=1, dp[1]=1
arr[1] > arr[0] -> 증가하는 수열이므로 Math.max(dp[0], dp[1]+1) -> 2 업데이트
ex) dp[0] -> {10} / dp[1]+1 -> {10, 20} 10으로 끝나는 부분수열에 20이 붙음

dp : [1, 2, 1, 1, 1]

 

 

 

 

 

 

 

 

i=2일때

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 1, 1]

j=0일때 arr[2]=10, arr[0]=10
arr[2] < arr[0] -> 증가하는 수열이 아니므로 dp 업데이트를 하지않음
dp : [1, 2, 1, 1, 1]


j=1일때 arr[2]=10, arr[1] 20
arr[2] < arr[1] -> 증가하는 수열이 아니므로 dp 업데이트를 하지 않음
dp : [1, 2, 1, 1, 1]

 

 

 

 

 

 

 

 

 

 

i=3일때

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 1, 1, 1]
j=0일때 arr[3]=30, arr[0]=10, dp[3]=1, dp[0]=1
arr[3] > arr[0] -> 증가하는 수열이 이므로 dp[3] = Math.max(dp[3], dp[0]+1) 업데이트
{10}으로 끝나는 부분수열에 -> {10, 30}으로 붙음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 2, 1, 1]
j=1일때 arr[3]=30, arr[1]=20, dp[3]=2, dp[1]=2
arr[3] > arr[1] -> 증가하는 수열이 이므로 dp[3] = Math.max(dp[3], dp[1]+1) 업데이트
{10, 20}의 부분수열에 -> {10, 20, 30}으로 붙음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 1, 1]
j=2일때 arr[3]=30, arr[2]=10, dp[3]=3. dp[2] = 1
arr[3] > arr[2] -> 증가하는 수열이 이므로 dp[3] = Math.max(dp[3], dp[2]+1) 업데이트
{20} 부분수열에 -> {20, 30}으로 붙었지만, 이미 30으로 끝나는 부분수열중
{10, 20, 30}의 원소의 개수가 더 많으므로 dp값은 변경되지 않음

 

 

 

 

 

 

 

 

 

 

 

i=4일때

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 1, 1]
j=0일때 arr[4]=20, arr[0]=10, dp[4]=1, dp[0]=1
arr[4] > arr[0] -> 증가하는 수열이므로 dp[4] = Math.max(dp[4], dp[0]+1) 업데이트
{10}으로 끝나는 부분수열에 -> {10,20}으로 붙음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 1]
j=1일때 arr[4]=20, arr[1]=20, dp[4]=2, dp[1]=2
arr[4] == arr[2] -> 증가하는 수열이 아니므로 그대로 유지
dp[4]의 가장 긴 증가하는 부분 수열은 {10, 20}임


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 1]
j=2일때 arr[4]=20, arr[2]=10, dp[4]=2. dp[2] = 1
arr[4] > arr[2] -> 증가하는 수열이므로 dp[4] = Math.max(dp[4], dp[2]+1) 업데이트
다만, 기존 dp[4] = {10, 20}과 새롭게 추가된 dp[2]+1{10, 40}이 동일하므로 업데이트를 하지 않음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 1]
j=3일때 arr[4]=20, arr[3]=30, dp[4]=2. dp[3] = 1
arr[4] < arr[3] -> 증가하는 수열이 아니므로 그대로 유지
dp[4]의 가장 긴 증가하는 부분 수열은 {10, 20}임

 

 

 

 

 

 

 

 

 

i=5일때

 

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 1]
j=0일때 arr[5]=50, arr[0]=10, dp[5]=1, dp[0]=1
arr[5] > arr[0] -> 증가하는 수열이므로 dp[5] = Math.max(dp[5], dp[0]+1) 업데이트
dp[5] = {10}으로 끝나는 부분수열에 -> {10,50}으로 붙음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 2]
j=1일때 arr[5]=50, arr[1]=20, dp[5]=2, dp[1]=2
arr[5] > arr[2] -> 증가하는 수열이므로 dp[5] = Math.max(dp[5], dp[1]+1) 업데이트
50으로 끝나는 부분수열에 기존 {10, 50}에 {20, 50}이 추가되었지만 원소의 개수는 동일하므로
dp[5]의 값은 변경되지 않음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 2]
j=2일때 arr[5]=50, arr[2]=10, dp[5]=2. dp[2] = 1
arr[5] > arr[2] -> 증가하는 수열이므로 dp[5] = Math.max(dp[5], dp[2]+1) 업데이트
위와 동일하게 {10, 50}, {20, 50}이 있기 때문에 원소의 개수가 동일하여
dp[5]의 값은 변경되지 않음


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 2]
j=3일때 arr[5]=50, arr[3]=30, dp[5]=2. dp[3] = 3
arr[5] > arr[3] -> 증가하는 수열이므로 dp[5] = Math.max(dp[5], dp[3]+1) 업데이트
dp[5] -> {10, 50}, {20, 50} / dp[3]+1 -> {10, 20, 30, 50} 기존 {10, 20, 30}에 붙음
원소의 개수가 4개인 {10, 20, 30 50}부분수열이 dp[5]의 가장 긴 증가하는 부분수열이 됨


arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 4]
j=4일때 arr[5]=50, arr[4]=20, dp[5]=4. dp[3] = 2
arr[5] > arr[3] -> 증가하는 수열이므로 dp[5] = Math.max(dp[5], dp[4]+1) 업데이트
dp[5] -> {10, 20, 30, 50} / dp[4]+1 -> {10, 20, 50} 이므로
기존 {10, 20, 30, 50}부분수열의 원소의 개수가 많아서 dp[5]는 변경되지 않음

 

 

 

 

 

 

 

 

 

 

arr의 모든 원소를 돌았기 때문에 for문은 종료된다.

최종 dp의 상태이다.

arr : {10, 20, 10, 30, 20 ,50 }
dp : [1, 2, 1, 3, 2, 4]

현재 dp의 마지막 원소가 가장 높지만, 마지막 항이 가장 높다라는 확신을 하면 안된다(지금은 마지막 원소(50)가 제일 커서 그럼)

arr의 LIS인 가장 긴 증가하는 부분수열의 개수를 구하려면 정렬을 사용하여 출력해야 된다.

 

 

        Arrays.sort(dp); // 이거 안해서 틀림 -> 마지막 노드가 부분 수열에 포함 안될 수 있음
        System.out.println(dp[N-1]);

이렇게 하면 최종 arr배열의 가장 긴 증가한은 부분수열의 원소의 개수가 출력된다.

참고로 가장 큰 부분 수열은 {10, 20, 30 ,50}이다.