N^2 방법
dp[i] = data[i] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이
for(int i=1; i<= N; i++)
{
for(int j=0; j < i; j++)
{
if(data[i] > data[j] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
}
}
result = max(result, dp[i]);
}
System.out.println(result);
Lower Bound 를 이용한 방법 / nlogn
dp 는 길이가 x인 최장증가수열의 마지막 수의 최소값을 의미
- 배열을 하나 생성해서 매번 수열을 구할때 마다 배열의 맨 뒤 원소와 현재 보고 있는 수열의 원소를 비교하여 수열의 원소가 더 클 시 배열 뒤에 push 해준 후 사이즈 +1
- 만약 수열의 원소가 배열의 맨 뒤 원소보다 작을 경우 lower_bound를 이용하여 최적의 자리를 찾은 뒤 그자리값을 해당 수열의 원소로 교체
ex ) 10, 20, 40, 30, 70, 50, 60
- 처음값 10을 넣어줌 : 배열의 최대 배열 사이즈 1
- 20 값은 배열 마지막 값인 10보다 크므로 배열 뒤에 추가 : 배열 사이즈 2
- 40 추가 : 배열 사이즈 3 / (10, 20, 40)
- 30 값은 배열의 마지막 값인 40보다 작으므로 lower_bound 를 이용하여 40자리에 30을 치환 / (10,20, 30)
- 70 추가 : 배열 사이즈 4 ( 10, 20, 30, 70)
- 50 값을 70과 치환 (10, 20, 30, 50) : 배열사이즈 4
- 60 추가 : 배열 사이즈 5 (10, 20, 30, 50, 60)
고려해야 할 부분
- 자기 뒤에 참조를 한다면 더 적은 값에서 참조를 하는 것이 유리하기 때문에 6번과 같이 70을 50과 치환이 가능
- 주의할 점은 dp 배열에 있는 값들은 LIS를 이루는 요소과 무관한 값들!! ( 수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색된 최적의 위치가 앞에 있을 수도 있기 때문!!)
size = 1;
dp[1] = data[1];
for(int i=2; i<= N; i++)
{
if(data[i] > dp[size]) // dp 맨뒤에 있는 자리와 비교하여 더 큰값이면 이어 붙이기
{
dp[++size] = data[i];
}
else if(data[i] < dp[size])
{
int tdx = lower_bound(1,size,data[i]);
dp[tdx] = data[i];
}
}
}
System.out.println(size);
lower_bound 방식 ( lis 요소들 추적 가능한 방법! )
실제 lis 배열을 구하는 알고리즘을 보자
예를들면 다음과 같다.
1 6 2 5 7 3 5 6인 경우
ans배열에는 다음과 같이 들어간다.
dx :: 0 1 1 2 3 2 3 4
dy :: 1 6 2 5 7 3 5 6
이 값을 dx를 기준으로 뒤에서 부터 조사해오면
dx가 4일때 (6) - > dx가 3일때 (5) -> dx가 2일때 (3)
-> dx가 1일때 (2) -> dx가 0일때(1)이다.
이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.
public class baek14002 {
static int N;
static int[] data = new int[1005];
static int[] dp = new int[1005];
static Node[] ans = new Node[1005];
static Deque<Integer> que = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
for(int i=1; i<= N; i++)
{
data[i] = Integer.parseInt(st.nextToken());
ans[i] = new Node(-1,-1);
}
dp[1] = data[1];
ans[1].dx = 1; // 실제 인덱스 1로 처음 시작
ans[1].dy = dp[1]; // 실제 값
int size = 1;
for(int i=2; i<= N; i++)
{
if(dp[size] < data[i])
{
dp[++size] = data[i];
ans[i].dx = size;
ans[i].dy = data[i];
}
else {
int idx = lower_bound(1, size, data[i]);
dp[idx] = data[i];
ans[i].dx = idx;
ans[i].dy = data[i];
}
}
System.out.println(size);
// 인덱스 i=2 부터 계속 해서 업데이트 해왔으므로
// 맨뒤 인덱스 부터 찾아 나감
int t = size;
for(int i = N; i > 0; i--)
{
if(t == ans[i].dx)
{
que.addLast(ans[i].dy);
t--;
}
}
while(!que.isEmpty())
{
int num = que.pollLast();
System.out.print(num+" ");
}
}
static class Node {
int dx, dy;
Node(int a, int b) {
dx=a; dy=b;
}
}
}
lower_bound 란?
- 이분 탐색을 통해 해당 위치를 return 해주는 방식
인덱스 트리를 이용한 방법 / nlogn
설명 : https://m.blog.naver.com/kks227/220791986409
(그림 확인)
- A[i] = x 값들을 모두 받아서 (x, i) pair 들을 만든 후 x 기준 오름차순 정렬
A[i]=x 인 i에 대해 구간 [0,i]에 지금까지 존재하는 lis 길이 +1이 x로 끝나는 lis 길이
주의 사항
- 중복된 값이 발생할 경우
==> 중복되는 값들 중에서는 가장 큰 인덱스 부터 방문해야 함!!!
==> 정렬할때 값 기준 오름차순 / 같은 값있을 경우는 인덱스 기준 내림차순
public class Main {
static int N, start, result;
static final int max_node = 500005;
static ArrayList<Node> arr = new ArrayList<>();
static int[] tree = new int[4*max_node];
static int[] dp = new int[max_node];
static Deque<Integer> que = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
N = Integer.parseInt(st.nextToken());
start = 1; result = 0;
int chk = 0; // 트리의 시작 인덱스를 찾기 위한 최대 노드 값
int dx = 0, dy = 0;
for(int i=1; i<= N; i++)
{
st = new StringTokenizer(br.readLine());
dx = Integer.parseInt(st.nextToken());
dy = Integer.parseInt(st.nextToken());
arr.add(new Node(dy,dx));
chk = max(chk, dx);
}
while(chk > start) start *= 2;
Collections.sort(arr, new mySort());
for(Node cur : arr)
{
int cnt = query(1, cur.idx); // 1 ~ i-1 까지의 최대 lis
update(cur.idx, cnt+1);
result = max(result, cnt+1);
dp[cur.idx] = cnt+1;
}
bw.write( (N-result) +"\n");
int size = result;
for(int i = chk; i > 0; i--)
{
if(dp[i] == 0) continue;
if(dp[i] == size) {
size--;
continue;
}
que.addLast(i);
}
while(!que.isEmpty())
{
int num = que.pollLast();
bw.write(num+"\n");
}
bw.flush();
}
public static void update(int idx, int num)
{
int s = start + idx - 1;
while(s > 0)
{
if(tree[s] < num)
{
tree[s] = num;
s /= 2;
}
else break;
}
}
public static int query(int sdx, int edx)
{
int ret = 0;
int s = start + sdx - 1;
int e = start + edx - 1;
while(s <= e)
{
if(s % 2 == 1)
{
if( ret < tree[s])
{
ret = tree[s];
}
}
if(e % 2 == 0)
{
if( ret < tree[e])
{
ret = tree[e];
}
}
s = (s+1) / 2;
e = (e-1) / 2;
}
return ret;
}
public static int max(int a, int b)
{
return a > b ? a : b;
}
static class mySort implements Comparator<Node>{ // 값에 대한 오름차순으로 정렬 하고 동일한 값이 있을 때는 인덱스가 큰 값 기준으로 내림 차순 정렬
@Override
public int compare(Node a, Node b) {
// TODO Auto-generated method stub
if(a.num < b.num) return -1;
else if(a.num > b.num) return 1;
else {
if(a.idx > b.idx) return -1;
else if(a.idx < b.idx) return 1;
else return 0;
}
}
}
static class Node {
int num, idx;
Node(int a, int b){
num=a; idx=b;
}
}
}
N^2 방법
dp[i] = data[i] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이
Lower Bound 를 이용한 방법 / nlogn
dp 는 길이가 x인 최장증가수열의 마지막 수의 최소값을 의미
ex ) 10, 20, 40, 30, 70, 50, 60
고려해야 할 부분
lower_bound 방식 ( lis 요소들 추적 가능한 방법! )
위의 방식은 LIS 길이를 구하는 방식이지만 해당 길이의 요소를 알수없다. ( 주의 )
ans 라는 pair 배열을 새로 만들고 정의해야함
ans[].dx : 실제 그 값이 들어갈수 있는 위치
ans[].dy : 실제 해당하는 값
실제 lis 배열을 구하는 알고리즘을 보자
예를들면 다음과 같다.
1 6 2 5 7 3 5 6인 경우
ans배열에는 다음과 같이 들어간다.
dx :: 0 1 1 2 3 2 3 4
dy :: 1 6 2 5 7 3 5 6
이 값을 dx를 기준으로 뒤에서 부터 조사해오면
dx가 4일때 (6) - > dx가 3일때 (5) -> dx가 2일때 (3)
-> dx가 1일때 (2) -> dx가 0일때(1)이다.
이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.
lower_bound 란?
인덱스 트리를 이용한 방법 / nlogn
설명 : https://m.blog.naver.com/kks227/220791986409
(그림 확인)
A[i]=x 인 i에 대해 구간 [0,i]에 지금까지 존재하는 lis 길이 +1이 x로 끝나는 lis 길이
주의 사항
==> 중복되는 값들 중에서는 가장 큰 인덱스 부터 방문해야 함!!!
==> 정렬할때 값 기준 오름차순 / 같은 값있을 경우는 인덱스 기준 내림차순