(25.04.12) DP vs LIS (Longest Increasing Subsequence)

 

최적의 경우의수를 나타내는 형태의 DP 알고리즘을 활용하는 문제인데, 
값들의 순서를 기억할 필요는 아니기 때문에,

DP로 백준문제에서 통과는 했지만,  LIS 알고리즘 이란 것을 검색하면서 우연히 알게 되어
이 문제에 적용을 해보았다.

---

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.
예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.
3 7 5 2 6 1 4
아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.
3 7 4 5 2 6 1
이제, 7번 아이를 맨 뒤로 옮긴다.
3 4 5 2 6 1 7
다음 1번 아이를 맨 앞으로 옮긴다.
1 3 4 5 2 6 7
마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.
1 2 3 4 5 6 7
위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.
N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

public class Main {

    public static void main(String args[]) throws Exception {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        int[] children = new int[n];
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(reader.readLine());
            children[i] = num;
        }

        // DP ( 값 : i 번째 까지 연속된 아이들의 최대의 수 )
        int[] dp = new int[n];

        // 초기값 등록
        Arrays.fill(dp, 1);

        // Children 순서대로 자기 앞이 자기보다 작으면 +1 추가
        // dp 값은 j dp값 과 비교했을 때
        for(int i = 1; i < n ; i++) {
            for(int j = 0; j < i; j++) {
                if(children[j] < children[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // dp 값중 최대 값 = 가장 긴 열 갯수 를 전체 수에서 뻄
        int result = 0;
        int maxLength = 0;
        for(int childrenLength : dp) {
            maxLength = Math.max(maxLength, childrenLength);
        }

        result = n - maxLength;
        System.out.println(result);
    }
}

• 가장 기초적인 DP지만, 문제의 포인트는 “ 연속된 순서열을 제외한 모든 요소의 위치는 1번 이상 바뀐다 “ DP 를 진행이 가능
  • 주의 : DP 값으로 바꾼 횟수 최솟값 아니고, 이렇게 설정을 하면 DP로 구할 수가 없음 → i 인덱스 뒤의 값을 제외하고 계산하기 때문에

LIS,Longest Increasing Subsequence 탐색법

• 최장 증가 부분 수열을 찾는 알고리즘을 활용하면 좀더 빠른시간복잡도를 가지고 효율적으로 작동시키게 할 수 있음
• ex) 3 7 5 2 6 1 4 수열에서 LIS 는 연속된 수열이 3 5 6 이기 때문에 3

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String args[]) throws Exception {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        int[] children = new int[n];
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(reader.readLine());
            children[i] = num;
        }

        // 최종 LIS 찾기
        List<Integer> lisList =  new ArrayList<>();

        for(int i = 0; i < n; i++) {
            int index = Collections.binarySearch(lisList, children[i]) ;

            // LIS 에 없을 경우 index 재지정
            if (index < 0) index = Math.abs(index) - 1;

            // index LIS 보다 작을 경우 -> 해당 위치 update 세팅
            if(index < lisList.size()) {
                lisList.set(index, children[i]);
            }

            // 크기랑 같거나 클 경우 뒤에 붙이기 -> 뒤에 세팅
            if(index >= lisList.size()) {
                lisList.add(children[i]);
            }
        }

        int result = n - lisList.size();

        System.out.println(result);
    }
}

• 계속 적으로 UPDATE 최신화로 최종 LIS 를 구하는 방식이기 때문에 실제 LIS 값을 활용할 수 없음
  • 크기가 같은데 안의 값들이 다를 수 있기 때문에
• 인덱스가 LIS 길이 보다 작으면 → 그냥 해당 인덱스 값 위치를 계속 UPDATE
  • (ArrayList).set(인덱스 위치, 값) 는 해당 위치에 UPDATED 하는 거지 뒤로 미루고 사이로 비집고 들어가는게 아님
• 인덱스가 LIS 보다 같거나 크면 → 새롭게 해당 위치에 UPDATE 가 아닌 추가

Collections.binarySearch(자료구조, 값)

• DP 를 사용하면 반복 순회이기 때문에 O(N^2) 시간 복잡도를 가지고있지만, Collecitons 자체의 binarySearch 메서드만으로 O(N log N) 의 효율적인 탐색이 가능
• 굳이 알고리즘으로 이분법 구현안해도, 메서드만으로도 구현이 가능
• 값이 자료구조에 없다면, 만약, 자료구조에 그 값이 있었더라면 있을 위치를 나타냄 (음수로)→ 따라서 인덱스 3으로 만드는 +1 작업이 필요
• ex) 1 2 3 5 구조에서 4를 찾고자 하면 -4 를 반환 (인덱스가 아님)

---

똑같은 의미지만, 기존에 활용을 해왔던 이분탐색 BinarySearch 메서드를 활용할 수 있다는 점이 매력적인 알고리즘이기 때문에 기억해 DP로 항상 알고리즘을 풀지 않아도 적용할 수있도록 해야겠다.