[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - C++ / JAVA

백준 12015 : 가장 긴 증가하는 부분 수열 2

등급 : Gold II

12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net)

12015번: 가장 긴 증가하는 부분 수열 2

사용 알고리즘 : Binary Search

사용 자료구조 : Vector

 

소위 LIS(Longest Increasing Subsequence)라고 알려진 이 문제는 동적 계획법과 이분 탐색으로 풀 수 있다.

이때, 전체적인 수열을 구하는 것이 아닌 횟수만 측정한다면, 이분 탐색으로 더 빠르게 결과를 구하는 것이 가능하다

 

4, 6, 7, 8, 1, 2, 5, 9가 순서대로 들어간다고 했을 때의 예시이다.

  · 직전 값보다 더 큰 경우 → 뒤에 삽입 

  · 직전 값보다 작은 경우 → lower_bound(값이 같거나 더 큰 가장 먼저 나오는 인덱스)에 현재 값을 대입

이 두가지 조건을 만족하게 하고, 배열의 길이를 구하게 되면 그 길이가 LIS의 길이가 된다.

C++에는 lower_bound를 구해주는 함수가 라이브러리에 구현이 되어 있지만, JAVA의 경우는 직접 구현해줘야 한다.

<hide/>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    vector <int> v, lis;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    lis.push_back(v[0]);
    for (int i = 1; i < n; i++)
    {
        if (v[i] > lis.back()) lis.push_back(v[i]);
        else
        {
            auto iter = lower_bound(lis.begin(), lis.end(), v[i]);
            *iter = v[i];
        }
    }
    cout << lis.size();
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {

    static int bi_search(int left, int right, int target, List<Integer> v)
    {
        while(left < right)
        {
            int mid = (left + right)/2;
            if(v.get(mid) >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }

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

        int n = Integer.parseInt(br.readLine());
        List<Integer> v = new ArrayList<>();
        List<Integer> LIS = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
            v.add(Integer.parseInt(st.nextToken()));
        }
        LIS.add(v.get(0));
        for(int i=1; i<n; i++)
        {
            if(LIS.get(LIS.size()-1) < v.get(i))
            {
                LIS.add(v.get(i));
            }
            else
            {
                LIS.set(bi_search(0, LIS.size()-1, v.get(i), LIS), v.get(i));
            }
        }
        System.out.println(LIS.size());
    }
}