99클럽 코테 스터디 31일차 TIL

백준 - 2631번

 

문제에서 옮겨진 번호는 4, 7, 1, 2번이다.

3, 5, 6 번은 그대로 있는데, 문제에 주어진 수열의 최장 증가 부분 수열(LIS)로 보인다.

N - (LIS 크기)를 하면 옮겨지는 아이의 최소 수를 구할 수 있다.

LIS를 구할 수 있는 방법 중 이분 탐색을 사용했다.

 

구현 1

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        int result = lis(arr, N);
        System.out.println(N - result);
    }

    private static int lis(int[] arr, int N) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(arr[0]);

        for (int i = 0; i < N; i++) {
            int tmp = arr[i];
            if (list.get(list.size() - 1) < tmp) {
                list.add(tmp);
            } else {
                int index = binarySearch(list, tmp);
                list.set(index, tmp);
            }
        }

        return list.size();
    }

    private static int binarySearch(ArrayList<Integer> list, int tmp) {
        int left = 0;
        int right = list.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (list.get(mid) < tmp) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

---

DP vs. Binary Search

1. 접근법

• DP :
  • 각 인덱스에서 끝나는 LIS의 길이를 구한다.
  • 배열을 순차적으로 탐색하며, 이전 값들과 비교하여 LIS를 갱신한다.
  • DP 배열의 최댓값은 전체 LIS 길이가 된다.
• 이분 탐색 :
  • 현재까지 LIS의 길이를 추적하는 배열을 유지한다.
  • 새 값을 배열에 이분 탐색으로 삽입하거나 대체하여 최적화한다.
  • LIS 길이는 배열의 크기로 결정된다.

2. 시간 복잡도

• DP :
  • O(n2) O(n^2) O(n2): 이전 모든 값을 탐색하며 최적의 값을 찾는다.
  • 개선된 DP로는 O(nlog⁡n)O(n \log n)O(nlogn)도 가능하지만, 기본 구현은 느리다.
• 이분 탐색 :
  • O(nlog⁡n)O(n \log n)O(nlogn): 이분 탐색으로 적절한 위치를 빠르게 찾고 갱신한다.

3. 특징

• DP 방식은 실제 LIS를 구할 때 유리하며, LIS를 역추적하기 쉽다.
• 이분 탐색 방식은 LIS 길이를 빠르게 구하는 데 최적화되어 있지만, 실제 LIS를 구현하려면 추가 작업이 필요하다. 

---

백준 2631번 - 줄 세우기

https://www.acmicpc.net/problem/2631