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

백준 - 1965번

상자를 넣을 수 있는 조건은 앞 상자 < 뒷 상자이다.

넣을 수 있는 상자의 개수가 최대가 되려면 뒤에 있는 상자 크기는 점점 늘어나야 한다.

• 예제 입력 1 : 1, 2, 3, 5, 6 -> 5
• 예제 입력 2 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 -> 10

문제에 주어진 수열에서 최장 증가 부분 수열(LIS)을 구하고 그 개수를 반환해야 한다.

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

최장 증가 부분 수열을 구현하는 방법으로는 DP와 이분 탐색이 있다.

 

구현 1 - DP

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] boxes = new int[n];
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            boxes[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1; // 상자 개수 초기화
        }
        br.close();

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

        System.out.println(result);
    }
}

dp 배열에 상자마다 담을 수 있는 최대 개수를 저장한다.

담을 수 있는 상자가 없는 경우, 자기 자신이 최대 개수이기 때문에 1로 초기화했다.

boxes [i] 값을 기준으로 반복문을 돌면서 해당 상자보다 작은 상자들인 경우 + 1 하여 최대 개수를 저장한다.

 

구현 2 - 이분 탐색

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

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[] boxes = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            boxes[i] = Integer.parseInt(st.nextToken());
        }
        br.close();

        int result = lis(boxes, n);
        System.out.println(result);
    }

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

        for (int i = 1; i < n; i++) {
            int tmp = boxes[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) {
                return mid;
            } else if (list.get(mid) < tmp) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

앞 상자 < 뒷 상자의 조건이 맞으면 list에 바로 저장되지만

앞 상자의 크기가 뒷 상자보다 크거나 같은 경우, 이분 탐색을 사용하여 저장할 위치를 찾는다.

 

2중 for문을 사용한 dp 방식은 모든 경우를 탐색하여 O(n^2)의 시간복잡도를 가지고,

이분 탐색 방식은 경우의 수를 1/2로 줄여 탐색하기 때문에 O(logn)의 시간 복잡도를 가진다.

---

백준 1965번 - 상자 넣기

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