[Coding Test] LIS

알고리즘 키워드
1. 
2. 
3. 

 

---

1. LIS 가 뭔데?

LIS == '가장 긴 증가하는 부분 수열'

 

    부분 수열 (Subsequence)

• 수열에서 일부 요소를 제거하고 남은 요소들이 원래 순서대로 나열된 것을 말한다.

 

• 일반적으로 정형화된 알고리즘이라기 보다는, 알면 좋은 자주나오는 개념이라고 생각하면 된다.

 

• 1. 가장 기본적으로 해결하는 방법은 DP 를 사용하는 방법이 있고 -> O(N^2)
  • 1) 수열의 각 위치에 대해서, 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아냄
  • 2) 이후 이를 바탕으로 전체 문제의 해답을 구함.
• 2. 보다 효율적인 이분탐색을 가지고 활용하는 방안이 있다. -> O(NlogN)
  • 1) 수열을 순차적으로 탐색하면서, 현재까지 발견된 가장 긴 증가하는 부분 수열을 유지한다.
  • 2) 새로운 요소가 나타나면, 이분탐색을 통해서 적절한 위치를 찾는다.
  • cf) 실제 LIS 요소들을 정확히 구성하지는 않지만, 가장 긴 증가하는 부분 수열의 길이를 효율적으로 사용할 수 있다.

 

2. LIS 를 푸는 코드

DP, BS 2가지로 푸는 방식을 나눌 수 있다.

• 1) DP 로 푸는 코드

public class LIS_DP {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        int[] dp = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }

        int maxLength = 0;
        for (int i = 0; i < N; i++) {
            dp[i] = 1; // 초기값은 자기 자신만으로 구성된 부분 수열
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1; // j번째 요소를 포함하는 경우의 수열 길이 갱신
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        System.out.println(maxLength);
        scanner.close();
    }
}

 

 

• BS (이진탐색) 으로 푸는 코드

public class LIS_BinarySearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        ArrayList<Integer> lis = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int num = scanner.nextInt();
            if (lis.isEmpty() || num > lis.get(lis.size() - 1)) {
                lis.add(num);
            } else {
                int left = 0, right = lis.size() - 1;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (lis.get(mid) >= num) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                lis.set(right, num);
            }
        }

        System.out.println(lis.size());
        scanner.close();
    }
}

 

 

 

 

 

3. LIS 문제인것을 판단하는 근거

중요한 포인트 4가지.

• 1. 순서가 중요한 수열
  • 문제에서 주어진 데이터가 순서를 유지해야 하는 수열 혹은 리스트.
  • 특히 요소들 간의 상대적인 순서가 결과에 영향을 미칠때.
• 2. 증가하는 부분
  • 문제 설명에 " 증가하는 부분수열", "가장 긴 상승하는 경로", "연속적이지 않아도 되는 증가 순서" 가 있다면.
• 3. 최대 길이 또는 최대 개수 찾기
  • 문제에서 어떤 조건을 만족하는 가장 긴 길이나 가장 많은 개수를 찾으라는 요구가 있을때
  • 이때 조건이 증가하는 순서와 관련되어 있다면, LIS 문제의 변형일 수 있다.
• 4. DP 나 BS 카테고리
  • 문제가 DP 나 BS 카테고리에 있다면, LIS 를 의심해보자.

 

 

🔎 예제 모음집 

LIS 예제 모음집

• 1) BOJ 12015 : 가장 긴 증가하는 부분 수열2
  • 이 문제는 DP 로 풀었을때, 시간초과가 난다. -> 그냥 이분탐색으로..?

 

• 2) BOJ 11568 : 민균이의 계략
  • 문제에서 LIS 라고 대놓고 적혀있음.

 

 

 

※ 출처 및 참고 내용 :