[Java] LIS, LCS

1. LIS란?

 

• Longest Increasing Subsequence
• 최장 증가 부분 수열
• 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만든다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 뜻한다.

 

---

2. LIS의 길이 구하기

 

동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자.

 

최장 증가 부분 수열

 

설명 참고.

 

---

가. O(N^2)

 

• 시간복잡도는 O(N^2)이다.

int lis(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n]; // 배열의 i번째 요소를 마지막으로 하는 LIS의 길이를 저장
    Arrays.fill(dp, 1); // lis의 길이는 최소 1 이상

    for (int i = 1; i < n; i++) { // 배열의 i번째 요소를 마지막으로 하는 최대 길이 저장
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int max = dp[0];
    for (int i = 1; i < n; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}

이 알고리즘에서, dp[i]는 배열의 i번째 요소를 마지막으로 하는 LIS의 길이를 저장한다.

 

배열의 모든 요소에 대해 dp[i]를 계산한 후, 그중 최댓값을 찾아서 반환한다.

 

---

나. O(NlogN)

 

• 시간복잡도는 O(NlogN)이다.

int lis(int[] arr) {
    int[] dp = new int[arr.length];
    int size = 0;
    for (int n : arr) {
        int point = Arrays.binarySearch(dp, 0, size, n);
        if (point < 0) point = -(point + 1);
        dp[point] = n;
        if (point == size) ++size;
    }
    return size;
}

이진 탐색을 사용하여 자신보다 큰 첫 번째 요소를 찾아서 덮어쓴다.

 

이때 dp는 오름차순으로 항상 정렬되어 있으므로 이진 탐색을 사용할 수 있다.

 

이진탐색을 arr.length만큼 수행하기 때문에 O(NlogN)의 시간복잡도를 가진다.

 

• if (point < 0) point = -(point + 1);
  : Arrays.binarySearch()에서 요소가 배열에 없으면 음수 값이 반환된다.
  : 해당 값보다 큰 첫 번째 요소의 위치를 반환한다.

💡 Arrays.binarySearch(byte[] a, int fromIndex, int toIndex, byte key) - 이진탐색을 한다. - 단, 찾는 값이 없으면 음의 정수를 반환한다. (-1이 아닐 수 있다.) - 키가 없을 때는 어느 위치에 넣어야 정렬 상태가 유지되는지 알려준다. - 반환된 값에서 -1을 곱하고 1을 뺀 값을 인덱스로 삽입하면 정렬이 유지된다. (-(idx+1))

---

다. 참고

 

Arrays.binarySearch()를 사용하지 않고 이진 탐색을 직접 구현한 코드다.

import java.util.ArrayList;
import java.util.Arrays;

public class LISTest {

    public static void main(String[] args) {
        int[] arr = {3,2,6,4,5,1};
        //        doLst1(arr);  // 2의 N승으로 구하기
        //        doLst2(arr);  // N 제곱으로 구하기
        doLst3(arr);  // NlongN으로 구하기
    }

    //    O(nLogn)으로 접근하기
    //    1. 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.
    //    2. 그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어갈 자리를 찾는다)
    static void doLst3(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = arr[0]; 
        int idx = 0; 
        System.out.println(Arrays.toString(dp));
        for (int i = 1; i < arr.length; i++) { 
            if (dp[idx] < arr[i]) { 
                dp[++idx] = arr[i]; 
            } else if(dp[idx] > arr[i]) { 
                int ii = lower_bound(dp, idx, arr[i]);
                dp[ii] = arr[i];
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(idx + 1);
    }
    static int lower_bound(int[] dp, int end, int n) {
        int start = 0;

        while (start < end) {
            int mid = (start + end) / 2;
            if (dp[mid] >= n) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
    //    O(n2) 으로 접근하기 - dp 기존에 얻어진 수보다 많은 횟수면 저장하고 다음숫자 비교함
    static void doLst2(int[] arr){
        int[] dp = new int[arr.length];
        for(int i = 0; i < dp.length; i++) {
            dp[i] = 1;
            for(int j = 1; j < i; j++) {
                if(arr[i] > arr[j] && dp[i] < dp[j]+1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        int max = Arrays.stream(dp).max().getAsInt();
        System.out.println(max);
    }
    //    완전 탐색으로 구하기
    static void doLst1(int[] arr) {
        int size = 1<<arr.length;
        System.out.println(size);
        ArrayList<Integer> list = new ArrayList<Integer>();
        int max = -1;
        int cnt = 0;
        for(int i = size-1; i > 0; i--) {
            list.clear();
            for(int j = 0; j < arr.length; j++) {
                if((i & 1<<j) != 0) {
                    list.add(arr[j]);
                }
            }
            max = Math.max(max, count(list, i));
            cnt++;
            if(i>>max == 0) {            
                break;
            }
        }
        System.out.println(max + " , cnt : " + cnt);
    }
    static int count(ArrayList<Integer> list, int j) {
        int size  = list.size();
        for(int i = 1 ; i < list.size(); i++) {
            if(list.get(i-1) > list.get(i)) {
                size = 1;
                break;
            }
        }
        if(size == list.size()) {
            System.out.println(list + " , " + j);
        }
        return size;
    }
}

 

---

2. LCS란?

 

• 최장 공통 부분수열(Longest Common Subsequence)
  : 두 문자열에서 가장 긴 공통의 연속된 문자열.
• 최장 공통 문자열(Longest Common Substring)
  : 두 문자열 모두의 부분수열이 되는 가장 긴 문자열.

 

---

가. Longest Common Substring

 

최장 공통 문자열(Longest Common Substring)은 두 문자열에서 가장 긴 공통의 연속된 문자열을 찾는 문제다.

 

동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있다.

 

int longestCommonSubstring(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    int[][] dp = new int[m+1][n+1];
    int result = 0; // 결과값 저장을 위한 변수

    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) { // 두 문자가 같다
                dp[i][j] = dp[i-1][j-1] + 1;
                result = Math.max(result, dp[i][j]);
            } else { // 두 문자가 다르다.
                dp[i][j] = 0;
            }
        }
    }

    return result;
}

두 문자열이 같은 문자를 가지면 dp[i][j] = dp[i-1][j-1] + 1;를 수행하여 현재까지의 공통 문자열의 길이를 증가시킨다.

 

그러나 두 문자열이 다른 문자를 가지면 dp[i][j] = 0;를 수행하여 공통 문자열의 길이를 0으로 초기화한다.

 

위에서 제시한 최장 공통 문자열 알고리즘의 시간 복잡도는 O(mn)이다.

 

여기서 m과 n은 각각 두 문자열의 길이를 의미한다.

 

---

나. Longest Common Subsequence

 

LCS는 두 개의 문자열이 주어졌을 때, 두 문자열 모두의 부분수열이 되는 가장 긴 문자열을 찾는 문제.

 

동적 계획법(Dynamic Programming)을 활용한다.

 

두 문자열의 모든 부분 문자열에 대한 LCS를 계산하고 이를 이용하여 전체 문자열의 LCS를 계산한다.

 

 

두 문자열의 길이를 각각 m, n이라고 하면, dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS의 길이를 저장한다.

 

이때, dp[0][j]와 dp[i][0]은 모두 0으로 초기화합니다.

 

int lcs(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    int[][] dp = new int[m+1][n+1];

    for (int i=1; i<=m; i++) { // 비교의 시작점
        for (int j=1; j<=n; j++) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) { // 두 문자가 같다.
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // 두 문자가 다르다.
            }
        }
    }

    return dp[m][n];
}

• if (str1.charAt(i-1) == str2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
  : 두 문자가 같은 경우.
  : dp[i-1][j-1] + 1를 저장한다.
  : 유일하게 값이 증가한다.
• else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
  : 두 문자가 다른 경우.
  : dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다.

 

위에서 제시한 LCS 알고리즘의 시간 복잡도는 O(mn)이다.

 

여기서 m과 n은 각각 두 문자열의 길이를 의미한다.

 

---