[백준문제풀이] 12015 가장 긴 증가하는 부분 수열2
https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
이 문제를 풀기 위해선
https://alotofsim.tistory.com/75
[TIL] LIS(최장증가수열) 에 대한 공부
dp문제를 풀다가 lis를 사용해야하는 문제가 나왔다. 예전에 알고특을 들을 때 그냥 가볍게 읽고 넘어간 내용이라 다시 떠오르려 하니 기억이 안 나는 상황 발생...(허걱) 완전히 이해하지 않고 그
alotofsim.tistory.com
이 지식이 필요하다.
N이 10^6 까지 값을 가질 수 있기 때문에 이를 dp문제로 풀게되면 이 문제는 O(N^2)의 시간 복잡도를 가지면서
제한시간 1초(1억)를 넘게 된다. 그래서 이 문제에선 최대한 시간복잡도를 O(NlogN) 로 만들어야한다.
그리고 이렇게 만드는 방법에는 두가지가 있다.
1. 바이너리서치 (이분탐색)
2. 세그먼트 트리
난 이 문제를 1로 풀었다.
문제를 풀며 가장 중요한것은
바이너리서치를 해야하는 조건을 아는 것 & 바이너리 서치 알고리즘을 짜는것!이라고 생각한다.
문제 예
만약 문제 값으로
7
10 30 20 50 40 10 60
이 들어오면, lis는 차례대로
0 10 0 0 0 0 0
0 10 30 0 0 0 0
0 10 20 0 0 0 0
0 10 20 50 0 0 0
0 10 20 40 0 0 0
0 10 20 40 0 0 0
0 10 20 40 60 0 0
로 갱신된다.
접근법 :
**1) 어떻게 풀 것인가?**
바이너리서치로 푼다.
**2) 시간복잡도**
O(NlogN)
**3) 공간복잡도**
512mb
**4) 풀면서 놓쳤던점**
바이너리 서치 알고리즘의 변형
**5) 이 문제를 통해 얻어갈 것**
lis를 바이너리서치로 푸는 법
import java.io.*;
public class Main {
static int[] lis;
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];
int idx, len = 0;
lis = new int[n+1];
String[] strings = br.readLine().split(" ");
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(strings[i]);
}
for(int i=0; i<n; i++){
if(arr[i]> lis[len]){
//lis의 가장 맨 끝에 있는 값보다 크다면 그냥 가장 뒤에 추가. [len+1]에 추가한단 뜻
len +=1;
lis[len] = arr[i];
}
else{
idx = binarySearch(0,len,arr[i]);
lis[idx] = arr[i];
}
}
System.out.println(len);
}
static int binarySearch(int low, int high, int key) {
int mid =0;
while(low<high) {
mid = (low+high)/2;
if(lis[mid] < key) {
low = mid+1;
}else {
high = mid;
}
}
return high;
}
}
만약 arr[i]의 값이 lis[mid] 보다 작거나 같다면 그것은 arr[i]가 들어갈곳은 mid의 왼쪽이라는 뜻이므로
high의 값을 mid로 잡고 다시 바이너리서치를 실행해야한다.
만약 arr[i]의 값이 lis[mid] 보다 크다면 그것은 arr[i]가 들어갈곳은 mid의 오른쪽이라는 뜻이므로
low의 값을 mid+1로 잡고 다시 바이너리서치를 실행해야한다.
이 코드에서 주의해야할것은
lis에서는 큰 값이 작은 값으로 갱신되지만,
작은 값이 큰 값으로 갱신되지 않는다는것이다.